답안 #65309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65309	2018-08-07T11:17:13 Z	zubec	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	31 ms	16936 KB

ricehub

#include <bits/stdc++.h>
using namespace std;

long long a[100100], pref[100100], n, L;

bool f(int x){
    for (int i = x; i <= n; i++){
        int l = i-x+1;
        int r = i;
        int mid = (l+r)>>1;
        long long sum = (pref[r]-pref[mid])-a[mid]*1ll*(r-mid);
        sum += a[mid]*1ll*(mid-l)-(pref[mid-1]-pref[l-1]);
        if (sum <= L)
            return 1;
    }
    return 0;
}


int besthub(int n, int L, int X[], long long B){
    ::n = n;
    for (int i = 0; i < n; i++)
        a[i+1] = X[i];
    for (int i = 1; i <= n; i++){
        pref[i] = pref[i-1] + a[i];
    }
    ::L = B;
    int l = 1, r = n;
    while(l < r){
        int mid = (l+r+1)>>1;
        if (f(mid))
            l = mid; else
            r = mid-1;
    }
    return l;
}

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	3 ms	588 KB	Output is correct
4	Correct	4 ms	720 KB	Output is correct
5	Correct	3 ms	732 KB	Output is correct

Subtask #2

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	908 KB	Output is correct
2	Correct	3 ms	936 KB	Output is correct
3	Correct	3 ms	940 KB	Output is correct
4	Correct	3 ms	944 KB	Output is correct
5	Correct	2 ms	948 KB	Output is correct
6	Correct	2 ms	952 KB	Output is correct
7	Correct	3 ms	956 KB	Output is correct
8	Correct	2 ms	960 KB	Output is correct
9	Correct	3 ms	960 KB	Output is correct
10	Correct	2 ms	968 KB	Output is correct
11	Correct	2 ms	972 KB	Output is correct
12	Correct	2 ms	976 KB	Output is correct
13	Correct	3 ms	1108 KB	Output is correct
14	Correct	3 ms	1108 KB	Output is correct
15	Correct	3 ms	1108 KB	Output is correct
16	Correct	3 ms	1108 KB	Output is correct
17	Correct	3 ms	1108 KB	Output is correct
18	Correct	3 ms	1108 KB	Output is correct
19	Correct	3 ms	1108 KB	Output is correct
20	Correct	3 ms	1108 KB	Output is correct
21	Correct	3 ms	1108 KB	Output is correct
22	Correct	2 ms	1108 KB	Output is correct
23	Correct	3 ms	1108 KB	Output is correct
24	Correct	3 ms	1108 KB	Output is correct
25	Correct	2 ms	1108 KB	Output is correct
26	Correct	3 ms	1108 KB	Output is correct
27	Correct	2 ms	1108 KB	Output is correct
28	Correct	3 ms	1108 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1108 KB	Output is correct
2	Correct	3 ms	1108 KB	Output is correct
3	Correct	4 ms	1108 KB	Output is correct
4	Correct	2 ms	1108 KB	Output is correct
5	Correct	3 ms	1108 KB	Output is correct
6	Correct	3 ms	1108 KB	Output is correct
7	Correct	4 ms	1112 KB	Output is correct
8	Correct	3 ms	1136 KB	Output is correct
9	Correct	4 ms	1236 KB	Output is correct
10	Correct	3 ms	1240 KB	Output is correct
11	Correct	2 ms	1240 KB	Output is correct
12	Correct	2 ms	1240 KB	Output is correct
13	Correct	2 ms	1240 KB	Output is correct
14	Correct	2 ms	1272 KB	Output is correct
15	Correct	2 ms	1272 KB	Output is correct
16	Correct	3 ms	1272 KB	Output is correct
17	Correct	3 ms	1272 KB	Output is correct
18	Correct	3 ms	1272 KB	Output is correct
19	Correct	2 ms	1272 KB	Output is correct
20	Correct	3 ms	1272 KB	Output is correct
21	Correct	3 ms	1336 KB	Output is correct
22	Correct	4 ms	1336 KB	Output is correct
23	Correct	4 ms	1432 KB	Output is correct
24	Correct	4 ms	1464 KB	Output is correct
25	Correct	3 ms	1496 KB	Output is correct
26	Correct	4 ms	1536 KB	Output is correct
27	Correct	3 ms	1576 KB	Output is correct
28	Correct	5 ms	1616 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	2040 KB	Output is correct
2	Correct	6 ms	2176 KB	Output is correct
3	Correct	20 ms	4748 KB	Output is correct
4	Correct	21 ms	5820 KB	Output is correct
5	Correct	12 ms	5820 KB	Output is correct
6	Correct	12 ms	5820 KB	Output is correct
7	Correct	30 ms	7300 KB	Output is correct
8	Correct	19 ms	8072 KB	Output is correct
9	Correct	15 ms	8072 KB	Output is correct
10	Correct	11 ms	8072 KB	Output is correct
11	Correct	28 ms	9676 KB	Output is correct
12	Correct	21 ms	10740 KB	Output is correct
13	Correct	13 ms	10740 KB	Output is correct
14	Correct	12 ms	10740 KB	Output is correct
15	Correct	18 ms	11812 KB	Output is correct
16	Correct	19 ms	12600 KB	Output is correct
17	Correct	31 ms	13916 KB	Output is correct
18	Correct	24 ms	14752 KB	Output is correct
19	Correct	21 ms	15936 KB	Output is correct
20	Correct	21 ms	16936 KB	Output is correct