oj.uz

Submission #1095905

# Submission time Handle Problem Language Result Execution time Memory
1095905 2024-10-03T11:42:10 Z dpsaveslives Balloons (CEOI11_bal) C++17
100 / 100
 140 ms 6992 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    stack<pair<double,double>> st;
    int N; cin >> N;
    vector<double> ans(N);
    for(int i = 0;i<N;++i){
        double x,r; cin >> x >> r;
        double res = r;
        while(!st.empty()){
            double bx = st.top().ff, rx = st.top().ss;
            double tmp = (x-bx)*(x-bx)/(4*rx);
            res = min(res,tmp);
            if(res >= rx){
                st.pop();
                continue;
            }
            break;
        }
        ans[i] = res;
        st.push({x,res});
    }
    cout << fixed << setprecision(3);
    for(int i = 0;i<N;++i){
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2128 KB 50000 numbers
2 Correct 29 ms 2132 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3684 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4212 KB 115362 numbers
2 Correct 80 ms 4432 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 5200 KB 154271 numbers
2 Correct 140 ms 6992 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 6224 KB 200000 numbers
2 Correct 115 ms 6992 KB 199945 numbers