Submission #634831

#	Time	Username	Problem	Language	Result	Execution time	Memory
634831		SharpEdged	Balloons (CEOI11_bal)	C++17	30 / 100	341 ms	5196 KiB

bal

/* Online C++ Compiler and Editor */
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

int main()
{
   int n; cin >> n;
   vector<double> x(n); vector<double> r(n);
   stack<pair<double, double>> mono;
   auto eval = [&](pair<double, double> prev, double x){
       return (prev.f - x) * (prev.f - x) / (4 * prev.s);
   };
   for (int i = 0; i < n; i++){
       cin >> x[i] >> r[i];
       while (!mono.empty()){
           double val = eval(mono.top(), x[i]);
           r[i] = min(r[i], val);
           if (mono.top().s <= val) {
               mono.pop();
           } else {
               break;
           }
       }
       mono.push({x[i], r[i]});
   }
   cout << fixed << setprecision(4) << '\n';
   for (int i = 0; i < n; i++) cout << r[i] << '\n';
   return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10