| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314309 | kingboy | Balloons (CEOI11_bal) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <stack>
using namespace std;
int main() {
int n;
cin >> n;
stack<pair<double, double>> st;
for (int x=0;x<n;x++) {
int xpos, maxRadius;
cin >> xpos >> maxRadius;
while (!st.empty()) {
double maxAllowableRadius = (x-st.top().first) * (x-st.top().first) / (4*st.top().second);
if (maxAllowableRadius <= maxRadius) {
maxRadius = maxAllowableRadius;
}
// covers previous balloon
if (maxRadius >= st.top().second) {
st.pop();
} else {
break;
}
}
cout << r << endl;
st.push({xpos, r});
}
}