oj.uz

Submission #1085287

# Submission time Handle Problem Language Result Execution time Memory
1085287 2024-09-07T20:48:48 Z LeonidCuk Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 1112 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<double>v1,v2,p1,p2,ans(100001);
double vidi(int n)
{
    double a=0;
    for(int i=0;i<=n;i++)
    {
        double b=min(p1[i],p2[n-i]);
        if(b>a)
        {
            a=b;
        }
    }
    return a-double(n);
}
int main()
{
    int n;
    double a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v1.push_back(a);
        v2.push_back(b);
    }
    sort(v1.begin(),v1.end(),greater<double>());
    sort(v2.begin(),v2.end(),greater<double>());
    p1.push_back(0);
    p2.push_back(0);
    for(int i=0;i<n;i++)
    {
        p1.push_back(p1[i]+v1[i]);
        p2.push_back(p2[i]+v2[i]);
    }
    ans[0]=0;
    ans[1]=vidi(1);
    ans[n]=vidi(n);
    ans[n-1]=vidi(n-1);
    int l=0,r=n/2,l1=0,r1=n/2-(n-1)%2;
    while(l<r)
    {
        int m=((l+r)/2)*2;
        ans[m]=vidi(m);
        if(ans[m]<ans[r*2])
        {
            l=m/2+1;
        }
        else
        {
            r=m/2;
        }
    }
    while(l1<r1)
    {
        int m=((l1+r1)/2)*2;
        ans[m+1]=vidi(m+1);
        if(ans[m+1]<ans[r1*2+1])
        {
            l1=m/2+1;
        }
        else
        {
            r1=m/2;
        }
    }
    cout<<fixed<<setprecision(4)<<max(ans[l*2],ans[l1*2+1]);
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1112 KB Output isn't correct
3 Halted 0 ms 0 KB -