Submission #231789

#	Time	Username	Problem	Language	Result	Execution time	Memory
231789		nicolaalexandra	Sure Bet (CEOI17_sure)	C++14	100 / 100	225 ms	5416 KiB

sure

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
double a[DIM],b[DIM],sp_a[DIM],sp_b[DIM];
int n,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i]>>b[i];

    sort (a+1,a+n+1);
    reverse (a+1,a+n+1);

    sort (b+1,b+n+1);
    reverse (b+1,b+n+1);

    for (i=1;i<=n;i++){
        sp_a[i] = sp_a[i-1] + a[i];
        sp_b[i] = sp_b[i-1] + b[i];
    }

    /// fixez cat iau din prima
    double maxi = 0;
    for (i=1;i<=n;i++){
        double sum1 = sp_a[i] - i;

        int st = 1, dr = n;
        while (st <= dr){
            int mid = (st+dr)>>1;
            double val1 = min (sum1 - mid + 1, sp_b[mid-1] - i - mid + 1);
            double val2 = min (sum1 - mid, sp_b[mid] - i - mid);
            double val3 = min (sum1 - mid - 1, sp_b[mid+1] - i - mid - 1);

            if (val1 <= val2 && val2 >= val3){
                maxi = max (maxi,val2);
                break;
            }

            if (val2 <= val3)
                st = mid+1;
            else dr = mid-1;
        }
    }

    cout<<setprecision(4)<<fixed<<maxi;

    return 0;
}

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