Submission #849513

#	Time	Username	Problem	Language	Result	Execution time	Memory
849513		Benmath	Sure Bet (CEOI17_sure)	C++14	100 / 100	122 ms	5996 KiB

sure

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;
int n;
double prvi[100010];
double drugi[100010];   
double prefiks[100010][3];
double sumiraj(int indeks, int koji){
    if(indeks == 0){
        return prefiks[n-1][koji];
    }else{
        return (prefiks[n-1][koji] - prefiks[indeks-1][koji]);
    }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> prvi[i];
        cin >> drugi[i];
    }
    sort(prvi, prvi+n);
    sort(drugi,drugi+n);
    double suma_prva = 0;
    double suma_druga = 0;
    prefiks[0][0] = prvi[0];
    prefiks[0][1] = drugi[0];
    for(int i = 1; i < n; i++){
        for (int j = 0; j < 2; j++){
            prefiks[i][j] = prefiks[i-1][j];
            if(j == 0){
                prefiks[i][j] += prvi[i];
            }else{
                prefiks[i][j] += drugi[i];
            }
        }
    }
    double ans = 0;
    for(int i = n-1; i>=0; i--){
        suma_prva = suma_prva + prvi[i];
        double broj_prvih = n-i;
        double broj_drugih = -1;
        int l = 0;
        int r = n-1;
        while (l <= r){
            int mid = (l+r) / 2;
            double mid1 = mid;
            if(sumiraj(mid,1) >= suma_prva){
                broj_drugih = max(broj_drugih , mid1);
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        broj_drugih = n - broj_drugih;
        if (broj_drugih != (n+1)){
             double rezultat = suma_prva - broj_prvih - broj_drugih;
            ans = max(ans, rezultat);
           // cout << ans << " "<<broj_prvih << " "<< broj_drugih << endl;
        }
    }
     for(int i = n-1; i>=0; i--){
        suma_druga = suma_druga + drugi[i];
        double broj_drugih = n-i;
        double broj_prvih = -1;
        int l = 0;
        int r = n-1;
        while (l <= r){
            int mid = (l+r) / 2;
            double mid1 = mid;
            if(sumiraj(mid,0) >= suma_druga){
                broj_prvih = max(broj_prvih,mid1);
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        broj_prvih = n - broj_prvih;
        if (broj_prvih != (n+1)){
            double rezultat = suma_druga - broj_prvih - broj_drugih;
            ans = max(ans, rezultat);
        }
    }
    
 printf("%.4lf",(double)ans);

}
  

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