Submission #1331813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1331813		Warinchai	Balloons (CEOI11_bal)	C++20	100 / 100	110 ms	5100 KiB

bal

#include<bits/stdc++.h>
#define int long double
using namespace std;

int g(pair<int,int>a,pair<int,int>b){
    return (a.first-b.first)*(a.first-b.first)/(4.0*b.second);
}

int rans[200005];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    deque<pair<int,int>>s;
    for(int32_t i=1;i<=n;i++){
        int a,b;cin>>a>>b;
        pair<int,int>cur={a,b};
        int r=b;
        while(!s.empty()){
            auto x=s.back();
            r=min(r,g(cur,x));
            if(r>=x.second)s.pop_back();
            else break;
        }
        s.push_back({a,r});
        rans[i]=r;
        //cerr<<r<<"\n";
        //while(s.size()>1&&g(cur,s[s.size()-2])<=g(cur,s[s.size()-1]))
    }
    for(int32_t i=1;i<=n;i++)cout<<fixed<<setprecision(3)<<rans[i]<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10