Submission #490955

#	Time	Username	Problem	Language	Result	Execution time	Memory
490955		socpite	Sure Bet (CEOI17_sure)	C++14	100 / 100	185 ms	4944 KiB

sure

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

int n;
vector<long double> A;
vector<long double> B;

int main(){
    long double ans = 0;
    cin >> n;
    A.assign(n+1, 0);
    B.assign(n+1, 0);
    for(int i = 1; i <= n; i++)cin >> A[i] >> B[i];
    sort(A.begin()+1, A.end());
    sort(B.begin()+1, B.end());
    reverse(A.begin()+1, A.end());
    reverse(B.begin()+1, B.end());
    for(int i= 1; i <= n; i++){
        A[i]+=A[i-1];
        B[i]+=B[i-1];
    }
    for(int i = 2; i <= 2*n; i++){
        int l = max(0, i-n), r = min(i, n), mid;
        long double tmp = i;
        while(r-l > 1){
            int mid = (l+r)>>1;
            ans = max(ans, min(A[mid], B[i-mid])-tmp);
            if(A[mid]-B[i-mid] > 0)r=mid;
            else l = mid;
        }
        ans = max(ans, min(A[l], B[i-l])-tmp);
        ans = max(ans, min(A[r], B[i-r])-tmp);
    }
    cout << fixed << setprecision(4) << ans;
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:23:45: warning: unused variable 'mid' [-Wunused-variable]
   23 |         int l = max(0, i-n), r = min(i, n), mid;
      |                                             ^~~

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