oj.uz

Submission #580960

# Submission time Handle Problem Language Result Execution time Memory
580960 2022-06-22T06:57:09 Z web Sure Bet (CEOI17_sure) C++17
60 / 100
 2000 ms 8040 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Execution timed out 2048 ms 8040 KB Time limit exceeded
18 Halted 0 ms 0 KB -