Submission #699451

#	Time	Username	Problem	Language	Result	Execution time	Memory
699451		vjudge1	Balloons (CEOI11_bal)	C++17	100 / 100	212 ms	11776 KiB

bal

#include <bits/stdc++.h>

using namespace std;
using lint = int64_t;
using ld = long double;

constexpr int _mod = int(1e9) + 7;
constexpr int _inf = 0x3f3f3f3f;
constexpr int _ninf = 0xcfcfcfcf;
constexpr lint _linf = 0x3f3f3f3f3f3f3f3f;

#define endl '\n'

int n;
vector<pair<ld,ld>> v;
stack<pair<ld,ld>> st;

ld solve(ld x, ld r) {
  while(!st.empty()) {
    auto [x1, r1] = st.top();
    r = min(r, ((x1 - x) * (x1 - x)) / (4 * r1));
    if(r1 > r) break;
    st.pop();
  }
  st.push({x, r});
  return r;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false); 

  cin >> n;

  v.resize(n);

  for(auto &i : v) {
    cin >> i.first >> i.second;
  };

  for(int i = 0; i < n; i++) {
    cout << fixed << setprecision(3) << solve(v[i].first, v[i].second) << endl;
  }
  
  return 0;
}

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