oj.uz

Submission #739718

# Submission time Handle Problem Language Result Execution time Memory
739718 2023-05-11T06:40:59 Z alexdd Seesaw (JOI22_seesaw) C++17
34 / 100
 2000 ms 33280 KB 
#include<bits/stdc++.h>
using namespace std;
//ifstream fin("seesaw.in");
//#define cin fin
#define double long double
vector<double> ord;
int n;
int a[200005];
double tot,ans=1000000000;
double verif(double le)///lungimea minima daca barycentrul nu poate trece in stanga lui le
{
    double sum = tot,mxm;
    int pozs=1,pozd=n;
    //mxm = tot/n;
    mxm = tot/n;
    for(int i=1;i<=n-1;i++)
    {
        if((sum-a[pozd])/(n-i)>=le)
        {
            sum-=a[pozd];
            pozd--;
        }
        else
        {
            sum-=a[pozs];
            pozs++;
        }
        mxm = max(mxm, sum/(n-i));
        //cout<<fixed<<setprecision(15)<<sum/(n-i)<<"\n";
    }
    ans = min(ans, mxm-le);
    return mxm-le;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tot+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        double cv = 0;
        for(int j=i;j<=n;j++)
        {
            cv += a[j];
            ord.push_back(cv/(j-i+1));
        }
    }
    sort(ord.begin(),ord.end());
    while(ord[ord.size()-1]>tot/n)
        ord.pop_back();
    /*for(int i=0;i<=19396720;i+=5000)
    {
        cout<<i<<" ";
        cout<<fixed<<setprecision(15)<<verif(i)<<"\n";
    }
    return 0;*/
    /*double st,dr,mij1,mij2;
    st=0;
    dr=tot/n;
    for(int i=0;i<100;i++)
    {
        mij1 = st + (dr-st)/3;
        mij2 = mij1 + (dr-st)/3;
        //if(verif(mij1)==verif(mij2)) cout<<"--- equal ---\n";
        if(verif(mij1)<verif(mij2))
            dr=mij2;
        else
            st=mij1;
    }*/
    int st,dr,mij1,mij2;
    st=0;
    dr=ord.size()-1;
    while(dr-st+1>=1000)
    {
        mij1 = st + (dr-st+1)/3;
        mij2 = mij1 + (dr-st+1)/3;
        if(verif(ord[mij1])<verif(ord[mij2]))
            dr=mij2;
        else
            st=mij1;
    }
    st=0;
    dr=ord.size()-1;
    for(int i=st;i<=dr;i++)
        ans = min(ans, verif(ord[i]));
    cout<<fixed<<setprecision(15)<<ans;
    return 0;
}
/**

100
2284149 9439055 9643266 21768889 29510678 35587049 62820950 78560461 81394668 95704920 107260947 114557772 133043762 149417332 154101416 159945788 176582178 186068138 186395727 191313484 230741882 238577339 256078675 266984273 288602592 298663330 300667425 312623432 320309556 330256868 330311884 335129852 338512525 342446297 365256477 365792687 369184784 374867618 390732627 443786820 460070486 469718485 484866399 485643582 491680703 493223721 495836723 499033340 499567053 500450312 511821689 526660122 539321234 541679322 549887263 550937124 571105693 571607050 591466920 599687686 631043668 635736592 642624962 645278333 649432665 673555823 674301968 679707485 703409317 706060309 706122169 742898252 768347394 777413859 778506544 807258074 808738343 813471215 816086870 818718023 827443027 829086443 829891568 832684678 836771534 838240547 848996536 852173500 859816999 866984866 870495040 876688933 894915786 913157273 916795811 922672202 931991270 940571890 979367890 981871060

correct output: 9396720.179007113

*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Execution timed out 2044 ms 33280 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Execution timed out 2044 ms 33280 KB Time limit exceeded
9 Halted 0 ms 0 KB -