Submission #407266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
407266	2021-05-18T16:50:08 Z	danielcm585	Rice Hub (IOI11_ricehub)	C++14	100 / 100	27 ms	3392 KB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
    
vector<ll> a, sum;

ll query(int l, int r) {
    l++, r++;
    return sum[r]-sum[l-1];
}

bool can(ll B, int l, int r) {
    int p = (l+r)/2;
    return a[p]*(p-l+1)-query(l,p) + query(p+1,r)-a[p]*(r-p) <= B;
}

int besthub(int R, int L, int X[], ll B) {
    int ans = 0;
    sort(X,X+R);
    sum.push_back(0);
    for (int i = 0; i < R; i++) {
        a.push_back(X[i]);
        sum.push_back(sum.back()+X[i]);
    }
    for (int i = 0; i < R; i++) {
        for (int l = i, r = R-1; l <= r; ) {
            int mid = (l+r)/2;
            if (can(B,i,mid)) {
                ans = max(ans,mid-i+1);
                l = mid+1;
            }
            else r = mid-1;
        }
    }
    return ans;
}

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	308 KB	Output is correct
4	Correct	1 ms	308 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct

Subtask #2

25.0 / 25.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
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	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	304 KB	Output is correct
21	Correct	1 ms	308 KB	Output is correct
22	Correct	1 ms	308 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	300 KB	Output is correct
28	Correct	1 ms	304 KB	Output is correct

Subtask #3

26.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	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	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	452 KB	Output is correct
22	Correct	2 ms	460 KB	Output is correct
23	Correct	2 ms	460 KB	Output is correct
24	Correct	2 ms	460 KB	Output is correct
25	Correct	2 ms	492 KB	Output is correct
26	Correct	2 ms	460 KB	Output is correct
27	Correct	2 ms	460 KB	Output is correct
28	Correct	2 ms	452 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	844 KB	Output is correct
2	Correct	5 ms	844 KB	Output is correct
3	Correct	27 ms	2496 KB	Output is correct
4	Correct	27 ms	2400 KB	Output is correct
5	Correct	12 ms	1388 KB	Output is correct
6	Correct	12 ms	1388 KB	Output is correct
7	Correct	24 ms	2488 KB	Output is correct
8	Correct	25 ms	2432 KB	Output is correct
9	Correct	13 ms	1396 KB	Output is correct
10	Correct	13 ms	1504 KB	Output is correct
11	Correct	26 ms	2420 KB	Output is correct
12	Correct	26 ms	2404 KB	Output is correct
13	Correct	12 ms	1516 KB	Output is correct
14	Correct	13 ms	1836 KB	Output is correct
15	Correct	20 ms	3136 KB	Output is correct
16	Correct	20 ms	3136 KB	Output is correct
17	Correct	26 ms	3376 KB	Output is correct
18	Correct	24 ms	3308 KB	Output is correct
19	Correct	25 ms	3348 KB	Output is correct
20	Correct	26 ms	3392 KB	Output is correct