oj.uz

Submission #211950

# Submission time Handle Problem Language Result Execution time Memory
211950 2020-03-21T19:50:36 Z csamoila Balloons (CEOI11_bal) C++14
100 / 100
 826 ms 5624 KB 
#include <iostream>
#include <stack>
#include <iomanip>

using namespace std;

int n;
stack < pair <int,double> > s;

double raza_maxima(int x,double r)
{
    while(!s.empty())
    {
        int x1=s.top().first;
        double r1=s.top().second;
        double rnou=(double)(x-x1)*(x-x1)/(double)(4*r1);
        //cout << rnou << '\n';
        //cout << s.size() << 'w';
        r=min(rnou,r);
        if(r<r1)
        {
            break;
        }
        s.pop();
    }
    s.push({x,r});
    return r;
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        double r;
        cin >> x >> r;
        cout << fixed << setprecision(3) << raza_maxima(x,r) << '\n';
    }
//    while(!s.empty())
//    {
//        cout << s.top().first << ' ' << s.top().second << '\n';
//        s.pop();
//    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 432 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 1016 KB 50000 numbers
2 Correct 205 ms 1660 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 1272 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 1572 KB 115362 numbers
2 Correct 492 ms 3576 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 2040 KB 154271 numbers
2 Correct 826 ms 5624 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 1888 KB 200000 numbers
2 Correct 816 ms 5552 KB 199945 numbers