oj.uz

Submission #872167

# Submission time Handle Problem Language Result Execution time Memory
872167 2023-11-12T12:10:50 Z 12345678 Balloons (CEOI11_bal) C++17
100 / 100
 119 ms 8696 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
double n, x[nx], dp[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x[i]>>dp[i];
    stack<pair<int, double>> s;
    for (int i=1; i<=n; i++)
    {
        while (!s.empty())
        {
            dp[i]=min(dp[i], (((x[i]-x[s.top().first])*(x[i]-x[s.top().first]))/(4*s.top().second)));
            if (dp[i]>=s.top().second) s.pop();
            else break;
        }
        printf("%.3f\n", dp[i]);
        s.push({i, dp[i]});
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3152 KB 50000 numbers
2 Correct 28 ms 3912 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3668 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3960 KB 115362 numbers
2 Correct 68 ms 5992 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4652 KB 154271 numbers
2 Correct 111 ms 8696 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5156 KB 200000 numbers
2 Correct 111 ms 8688 KB 199945 numbers