Submission #1158005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158005		ocasu	Sure Bet (CEOI17_sure)	C++20	60 / 100	78 ms	3400 KiB

sure

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MUL=1e12;

signed main(){
    int n; cin>>n;
    vector<int> a(n),b(n);
    for (int i=0; i<n; i++) {
        double x,y; cin>>x>>y;
        a[i]=x*MUL, b[i]=y*MUL;
    }
    sort(a.begin(),a.end(),greater<int>()), sort(b.begin(),b.end(),greater<int>());
    vector<int> pa(n), pb(n);
    pa[0]=a[0], pb[0]=b[0];
    for (int i=1; i<n; i++) pa[i]=pa[i-1]+a[i], pb[i]=pb[i-1]+b[i];
    int ans=0;
    for (int i=0; i<n; i++){
        //cout<<pa[i]<<' ';
        int sA = pa[i];
        //binary search in min size subset in B that is >= sA
        int ind=lower_bound(pb.begin(),pb.end(),sA) - pb.begin();
        if (ind<n) {
            ans=max(ans, sA -MUL*( i+1 + ind+1));
            //cout<<"A: "<<i<<' '<<(i+1+ind+1)<<'\n';
        }
    }
    //cout<<'\n';
    for (int i=0; i<n; i++){
        int sB = pb[i];
        //binary search in min size subset in B that is >= sA
        int ind=lower_bound(pa.begin(),pa.end(),sB) - pa.begin();
        if (ind<n) {
            ans=max(ans, sB - MUL*( i+1 + ind+1));
            //cout<<"B: "<<i<<' '<<(i+1+ind+1)<<'\n';

        }
    }
    double x = ((double)ans/MUL);
    printf("%.4lf",(double)x);
}   

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 40