oj.uz

Submission #307677

# Submission time Handle Problem Language Result Execution time Memory
307677 2020-09-29T04:51:52 Z juggernaut Rice Hub (IOI11_ricehub) C++14
0 / 100
 4 ms 768 KB 
#include"ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[100005];
ll b,pref[100005],suff[100005];
ll pref_calc(int l,int r){
    return pref[r]-(l-1)*(a[r]-a[l-1]);
}
ll suff_calc(int l,int r){
    return suff[l]-(n-r)*(a[r+1]-a[l]);
}
bool app(int l,int r){
    int i=(l+r)>>1;
    ll mn=pref_calc(l,i)+suff_calc(i,r);
    return mn<=b;
}
bool check(int x){
    bool flag=0;
    for(int i=1;i+x-1<=n;i++)flag|=app(i,x+i-1);
    return flag;
}
int besthub(int N,int L,int A[],ll B){
    n=N;b=B;
    for(int i=0;i<n;i++)a[i+1]=A[i];
    for(int i=1;i<=n;i++)
        pref[i]=pref[i-1]+(i-1)*(a[i]-a[i-1]);
    for(int i=n;i>=1;i--)
        suff[i]=suff[i+1]+(n-i)*(a[i+1]-a[i]);
    int l=1,r=n,m;
    while(l<r){
        m=(l+r+1)>>1;
        if(check(m))l=m;
        else r=m-1;
    }
    return l;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -