Submission #340196

#	Time	Username	Problem	Language	Result	Execution time	Memory
340196		blue	Sure Bet (CEOI17_sure)	C++11	100 / 100	187 ms	3692 KiB

sure

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

/*
a[i] >= a[i+1]
b[i] >= b[i+1]

To maximise: min(a[1] + ... + a[i], b[1] + ... + b[j]) - (i + j)
*/

int main()
{
    int n;
    cin >> n;

    double a[n], b[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        a[i] = -1.0 * a[i];
        b[i] = -1.0 * b[i];
    }
    sort(a, a+n);
    sort(b, b+n);

    double res = 0.0;

    int A = 0, B = 0;
    double asum = 0.0, bsum = 0.0;

    while(A+B < 2*n)
    {
        if(A == n)
        {
            bsum -= b[B];
            B++;
        }
        else if(B == n)
        {
            asum -= a[A];
            A++;
        }
        else if(asum == bsum)
        {
            if(-a[A] > -b[B])
            {
                asum -= a[A];
                A++;
            }
            else
            {
                bsum -= b[B];
                B++;
            }
        }
        else if(asum > bsum)
        {
            bsum -= b[B];
            B++;
        }
        else
        {
            asum -= a[A];
            A++;
        }
        res = max(res, min(asum, bsum) - double(A+B));
    }
    printf("%.4lf",(double)res);
}

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