oj.uz

Submission #1118876

# Submission time Handle Problem Language Result Execution time Memory
1118876 2024-11-26T10:32:18 Z kfhjad Balloons (CEOI11_bal) C++17
100 / 100
 148 ms 5972 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N;
    cin >> N;
    
    stack<pair<ll, long double>> mono;
    mono.push({-1e9, 1});
    
    cout << fixed << setprecision(5);
     
    while (N--)
    {
        ll x;
        long double r;
        cin >> x >> r;
        
        while (!mono.empty())
        {
            auto [x1, r1] = mono.top();
            long double newR = (x - x1) * (x - x1) / (4 * r1);
            r = min(r, newR);
            
            if (r < r1)
                break;
            
            mono.pop();
        }
        
        cout << r << '\n';
        mono.push({x, r});
    }
	
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 2 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1836 KB 50000 numbers
2 Correct 33 ms 1868 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3148 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 3616 KB 115362 numbers
2 Correct 95 ms 3660 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4428 KB 154271 numbers
2 Correct 121 ms 5972 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 5084 KB 200000 numbers
2 Correct 148 ms 5964 KB 199945 numbers