Submission #148086

#	Time	Username	Problem	Language	Result	Execution time	Memory
148086		WhipppedCream	Sure Bet (CEOI17_sure)	C++17	100 / 100	238 ms	3644 KiB

sure

//
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vvi vector< vi >
#define vii vector< ii >
#define mp make_pair
#define pb push_back
const int maxn = 1e5+5;
double A[maxn], B[maxn];
int n;
double solve(int k)
{
    int lo = max(0, k-n), hi = min(n, k);
    double best = -1e9;
    while(lo<= hi)
    {
        int mid = (lo+hi)/2;
        //printf("%d %d\n", lo, hi);
        double x = A[mid];
        double y = B[k-mid];
        //printf("%.4lf %.4lf\n", x, y);
        if(x == y) return x;
        best = max(best, min(x, y));
        if(x< y) lo = mid+1;
        else hi = mid-1;
    }
    //printf("%d: %.4lf\n", k, best);
    return best;
}
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    scanf("%d", &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);
    reverse(A+1, A+n+1); reverse(B+1, B+n+1);
    for(int i = 1; i<= n; i++)
    {
        A[i] += A[i-1]; B[i] += B[i-1];
        //cout << A[i] << " " << B[i] << endl;
    }
    double best = 0;
    for(int i = 1; i<= 2*n; i++) best = max(best, solve(i)-i);
    printf("%.4lf\n", best);
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

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