oj.uz

Submission #49436

# Submission time Handle Problem Language Result Execution time Memory
49436 2018-05-28T23:57:43 Z ho94949 Rice Hub (IOI11_ricehub) C++17
100 / 100
 22 ms 15732 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-1, B)) lo = mi; //tweak, make X 1-indexed
        else hi = mi;
    }
    return lo;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 804 KB Output is correct
15 Correct 2 ms 804 KB Output is correct
16 Correct 2 ms 804 KB Output is correct
17 Correct 2 ms 804 KB Output is correct
18 Correct 3 ms 804 KB Output is correct
19 Correct 3 ms 804 KB Output is correct
20 Correct 2 ms 804 KB Output is correct
21 Correct 2 ms 804 KB Output is correct
22 Correct 2 ms 804 KB Output is correct
23 Correct 2 ms 804 KB Output is correct
24 Correct 2 ms 804 KB Output is correct
25 Correct 2 ms 804 KB Output is correct
26 Correct 2 ms 804 KB Output is correct
27 Correct 2 ms 804 KB Output is correct
28 Correct 2 ms 804 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 804 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 2 ms 804 KB Output is correct
4 Correct 2 ms 868 KB Output is correct
5 Correct 2 ms 868 KB Output is correct
6 Correct 2 ms 868 KB Output is correct
7 Correct 2 ms 900 KB Output is correct
8 Correct 2 ms 924 KB Output is correct
9 Correct 3 ms 924 KB Output is correct
10 Correct 2 ms 924 KB Output is correct
11 Correct 2 ms 956 KB Output is correct
12 Correct 2 ms 956 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Correct 2 ms 980 KB Output is correct
15 Correct 2 ms 984 KB Output is correct
16 Correct 2 ms 984 KB Output is correct
17 Correct 2 ms 984 KB Output is correct
18 Correct 3 ms 1004 KB Output is correct
19 Correct 2 ms 1012 KB Output is correct
20 Correct 2 ms 1020 KB Output is correct
21 Correct 3 ms 1152 KB Output is correct
22 Correct 3 ms 1152 KB Output is correct
23 Correct 2 ms 1152 KB Output is correct
24 Correct 3 ms 1152 KB Output is correct
25 Correct 3 ms 1156 KB Output is correct
26 Correct 3 ms 1188 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 3 ms 1324 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1444 KB Output is correct
2 Correct 17 ms 1544 KB Output is correct
3 Correct 20 ms 3492 KB Output is correct
4 Correct 20 ms 4560 KB Output is correct
5 Correct 10 ms 4560 KB Output is correct
6 Correct 10 ms 4724 KB Output is correct
7 Correct 16 ms 6016 KB Output is correct
8 Correct 16 ms 6820 KB Output is correct
9 Correct 11 ms 6820 KB Output is correct
10 Correct 9 ms 6820 KB Output is correct
11 Correct 22 ms 8424 KB Output is correct
12 Correct 19 ms 9488 KB Output is correct
13 Correct 11 ms 9488 KB Output is correct
14 Correct 17 ms 9660 KB Output is correct
15 Correct 16 ms 10740 KB Output is correct
16 Correct 15 ms 11528 KB Output is correct
17 Correct 19 ms 12708 KB Output is correct
18 Correct 19 ms 13736 KB Output is correct
19 Correct 18 ms 14712 KB Output is correct
20 Correct 19 ms 15732 KB Output is correct