Submission #800982

#	Time	Username	Problem	Language	Result	Execution time	Memory
800982		vjudge1	Sure Bet (CEOI17_sure)	C++11	100 / 100	73 ms	3456 KiB

sure

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <deque>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <iomanip>
using namespace std;
using lli = long long;
using ldb = long double;
const int maxN = 1e5;
ldb a[maxN + 1];
ldb b[maxN + 1];
ldb ps[maxN + 1];
int n;

ldb Calc(ldb resa, ldb resb, int pb)
{
    if (resb >= resa)
        return resb;
    int low = pb;
    int high = n;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (resa - (mid - pb + 1) >= resb + ps[mid] - ps[pb - 1] - (mid - pb + 1))
            low = mid + 1;
        else
            high = mid - 1;
    }
    --low;
    resa -= (low - pb + 1);
    resb += ps[low] - ps[pb - 1] - (low - pb + 1);
    ldb res = resb;
    if (low < n)
        res = max(res, resa - 1);
    return res;
}

int main()
{
#ifdef LeMinhDuc
    freopen("inp.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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);

    ldb ans = 0;
    int cnt = 0;
    ldb resa = 0;
    ldb resb = 0;
    int c1 = n;
    int c2 = n;

    while(true)
    {
        if (c1 == 0 && c2 == 0) break;
        if(c1 == 0)
        {
            resb += b[c2];
            c2--;
            cnt++;
        }
        else if(c2 == 0)
        {
            resa += a[c1];
            c1--;
            cnt++;
        }
        else if (resa < resb)
        {
            resa += a[c1];
            c1--;
            cnt++;
        }
        else if (resa > resb)
        {
            resb += b[c2];
            c2--;
            cnt++;
        }
        else if (resa == resb)
        {
            if (c2 == 0 || a[c1] > b[c2])
            {
                resa += a[c1];
                c1--;
                cnt++;
            }
            else if(c1 == 0 || a[c1] <= b[c2])
            {
                resb += b[c2];
                c2--;
                cnt++;
            }
        }
        long double res = min(resa - cnt , resb - cnt);
        ans = max(ans , res);
    }
    cout<<fixed << setprecision(4) <<ans;
}

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