oj.uz

Submission #411655

# Submission time Handle Problem Language Result Execution time Memory
411655 2021-05-25T16:50:41 Z A_D Rice Hub (IOI11_ricehub) C++14
17 / 100
 16 ms 2252 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL NN=1e5+100;
LL a[NN];
LL pre[NN];
LL n,b;
bool ok(LL mid)
{
    LL l=1,r=mid,me=0;
    while(r<=n){
        LL avg=(pre[r]-pre[l-1])/mid;
        while(a[me+1]<=avg&&me<n){
            me++;
        }
        LL ret=avg*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-avg*(r-me);
        if(ret<=b)return 1;
        avg++;
        while(a[me+1]<=avg&&me<n){
            me++;
        }
        ret=avg*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-avg*(r-me);
        if(ret<=b)return 1;
        l++;
        r++;
    }
    return 0;
}
int besthub(int R, int L, int X[], long long B)
{
    n=R;
    b=B;
    for(LL i=0;i<R;i++)a[i+1]=X[i];
    for(LL i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    LL l=1,r=n,ans=0;
    while(l<=r){
//        cout<<5<<endl;
        LL mid=(l+r)/2;
        if(ok(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    int ann=ans;
    return ann;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 704 KB Output is correct
2 Correct 7 ms 588 KB Output is correct
3 Correct 15 ms 2144 KB Output is correct
4 Correct 16 ms 2252 KB Output is correct
5 Correct 12 ms 1292 KB Output is correct
6 Correct 12 ms 1268 KB Output is correct
7 Correct 14 ms 2232 KB Output is correct
8 Correct 14 ms 2164 KB Output is correct
9 Correct 12 ms 1204 KB Output is correct
10 Incorrect 11 ms 1200 KB Output isn't correct
11 Halted 0 ms 0 KB -