Submission #561208

#	Time	Username	Problem	Language	Result	Execution time	Memory
561208		NintsiChkhaidze	Sure Bet (CEOI17_sure)	C++14	100 / 100	89 ms	5248 KiB

sure

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
 
const int N = 100005;
double a[N],b[N],A[N],B[N];

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    
    for (int i = 1; i <= n; i++)
        cin>>a[i]>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    
    for (int i = n; i >= 1; i--){
        A[i] = A[i + 1] + a[i];
        B[i] = B[i + 1] + b[i];
    }
    double ans = 0.0;
    for (int i = n; i >= 1; i--){
        int l = 1,r = n,res=0;
        while(l <= r){
            int mid = (l+r)>>1;
            if (B[mid] >= A[i]) {
                res = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        int tot = 2*n - i + 2 - res;
        if (res && A[i] - tot > ans)
            ans = A[i] - tot;
    }
    for (int i = n; i >= 1; i--){
        int l = 1,r = n,res=0;
        while(l <= r){
            int mid = (l+r)>>1;
            if (A[mid] >= B[i]) {
                res = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        int tot = 2*n - i + 2 - res;
        if (res && B[i] - tot > ans)
            ans = B[i] - tot;
    }
    printf("%.4f",ans);
}

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