oj.uz

Submission #49435

# Submission time Handle Problem Language Result Execution time Memory
49435 2018-05-28T23:53:49 Z ho94949 Rice Hub (IOI11_ricehub) C++17
0 / 100
 9 ms 1520 KB 
#include "ricehub.h"

bool can(int g, int N, long long S[], int X[], long long B)
{
    for(int l=1; l<=N-g+1; ++l)
    {
        //[l, r]
        int r = l+g-1; 
        int m = (l+r)/2;
        
        //[l, m-1]
        long long lsum = (long long)(m-l)*X[m] - (S[m-1] - S[l-1]);
        //[m+1, r]
        long long rsum = (S[r] - S[m]) - (long long)(r-m)*X[m];
        if(lsum+rsum <= B) return true;
    }
    return false;
}

int besthub(int R, int L, int X[], long long B)
{
    long long *S = new long long[R+1];
    S[0] = 0;
    for(int i=1; i<=R; ++i)
        S[i] = S[i-1] + X[i-1];
    int lo = 0; //pos
    int hi = R+1; //impos
    while(lo+1!=hi)
    {
        int mi = (lo+hi)/2;
        if(can(mi, R, S, X, B)) lo = mi;
        else hi = mi;
    }
    return lo;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

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