oj.uz

Submission #930541

# Submission time Handle Problem Language Result Execution time Memory
930541 2024-02-20T05:57:48 Z phlap Balloons (CEOI11_bal) C++17
100 / 100
 117 ms 11860 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M=998244353;

void solve(){
  int x;
  cin>>x;
  pair<int, int> arr[x];
  long double ans[x];
  for(int i=0; i<x; i++){
    cin>>arr[i].first>>arr[i].second;
  }
  stack<pair<int, long double>> s;
  for(int i=0; i<x; i++){
    long double r=arr[i].second;
    while(!s.empty()){
      r=min(r, (arr[i].first-s.top().first)*(arr[i].first-s.top().first)/(4*s.top().second));
      if(r>=s.top().second) s.pop();
      else break;
    }
    ans[i]=r;
    s.push({arr[i].first, ans[i]});
  }
  for(int i=0; i<x; i++) cout<<fixed<<setprecision(3)<<ans[i]<<'\n';
}
 
signed main(){
  //freopen("in", "r", stdin); //freopen("out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  int t=1; //cin>>t;
  while(t--) solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1416 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3300 KB 50000 numbers
2 Correct 26 ms 3164 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5972 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6876 KB 115362 numbers
2 Correct 62 ms 7312 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 9096 KB 154271 numbers
2 Correct 104 ms 11812 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10836 KB 200000 numbers
2 Correct 106 ms 11860 KB 199945 numbers