oj.uz

Submission #699451

# Submission time Handle Problem Language Result Execution time Memory
699451 2023-02-17T02:56:53 Z vjudge1 Balloons (CEOI11_bal) C++17
100 / 100
 212 ms 11776 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1020 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2660 KB 50000 numbers
2 Correct 48 ms 3168 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 4556 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 5296 KB 115362 numbers
2 Correct 116 ms 7152 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 6732 KB 154271 numbers
2 Correct 205 ms 11776 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 8140 KB 200000 numbers
2 Correct 212 ms 11696 KB 199945 numbers