Submission #841780

#	Time	Username	Problem	Language	Result	Execution time	Memory
841780		vjudge1	Sure Bet (CEOI17_sure)	C++17	100 / 100	70 ms	5292 KiB

sure

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

const int maxn = 1e5 + 5;

int n;
double a[maxn], b[maxn];
double sum_1[maxn], sum_2[maxn];
double kq;

bool cmp(double a, double b)
{
    return (a > b);
}

bool check(int mid, int id)
{
    double cur = sum_1[id] - (mid + id);
    double val = sum_2[mid] - (mid + id);

    if(val >= cur)
        return true;
    return false;
}

signed main()
{
//    freopen("B.inp", "r", stdin);
//    freopen("B.out", "w", stdout);

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

    sort(a+1, a+1+n, cmp);
    sort(b+1, b+1+n, cmp);

    for(int i=1 ; i<=n ; ++i){
        sum_1[i] = sum_1[i-1] + a[i];
        sum_2[i] = sum_2[i-1] + b[i];
    }

    for(int i=1 ; i<=n ; ++i){
        int l=0;
        int r=n;

        while(r - l > 1){
            int mid = l + r >> 1;
            if(check(mid, i)){
                r = mid;
            }
            else{
                l = mid;
            }
        }

        double val = min(sum_2[r] - (r + i), sum_1[i] - (r + i));
        kq = max(kq, val);
        if(r > 1){
            val = min(sum_2[r-1] - (r + i - 1), sum_1[i] - (r + i - 1));
            kq = max(kq, val);
        }
    }

   cout << setprecision(4) << fixed << kq;
}

/// code by yourlove ///

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:52:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |             int mid = l + r >> 1;
      |                       ~~^~~

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