Submission #580960

#	Time	Username	Problem	Language	Result	Execution time	Memory
580960		web	Sure Bet (CEOI17_sure)	C++17	60 / 100	2048 ms	8040 KiB

sure

#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

void output(double p1, double p2)
{
    if(p1 < 0 ||p2<0)
         printf("%.4lf", (double)(0));
    else
        printf("%.4lf", (double)(min(p1, p2)));
}

long double ternarySearch(vector<long double> prefSum2, int minK, int maxK, long double deficit, long double profPure1)
{
    int r = maxK, l = minK;
    while(r-l > 3)
    {
        int m1 = l + (r-l)/3;
        int m2 = r - (r-l)/3;
        long double part1fM1 = profPure1 - m1-1;
        long double part2fM1 = prefSum2[m1] + deficit  - m1-1;
        long double fm1 = min(part1fM1, part2fM1);
        long double part1fM2 = profPure1 - m2-1;
        long double part2fM2 = prefSum2[m2] + deficit - m2- 1;
        long double fm2 = min(part1fM2, part2fM2);
        if(fm1 < fm2)
        {
            l = m1;
        }
        else
        {
            r = m2;
        }
    }

    long double bestVal = 0;
    for(int i = l; i<= r; ++i)
    {
        long double part1 = profPure1 - i-1;
        long double part2 = prefSum2[i] + deficit  - i-1;
        long double f =min(part1, part2);
        if(f > bestVal)
            bestVal = f;
    }
    return bestVal;
}

int main()
{
    int n; cin>>n;
    vector<long double> odds1(n), odds2(n);
    for(int i = 0; i<n; ++i)
    {
        cin>>odds1[i]>>odds2[i];
    }
    sort(odds1.rbegin(), odds1.rend());
    sort(odds2.rbegin(), odds2.rend());
    vector<long double> prefSum1(n);
    vector<long double> prefSum2(n);
    prefSum1[0] = odds1[0];
    prefSum2[0] = odds2[0];
    for(int i  =1; i<n; ++i)
    {
        prefSum1[i] = prefSum1[i-1]+odds1[i];
        prefSum2[i] = prefSum2[i-1]+ odds2[i];
    }
    long double bestSureProf = 0;

    for(int i = 0; i<n; ++i)
    {
        long double best = ternarySearch(prefSum2, 0, n-1, -i-1, prefSum1[i]-i-1);
        if(best > bestSureProf)
            bestSureProf = best;
    }
    output(bestSureProf, bestSureProf);
    
    return 0;
}

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