#include <bits/stdc++.h>
using namespace std;
#define int long long
int range_len[2000005];
pair<int,int> memo[2005][2005];
int N,D,T;
pair<int,int> operator+ (pair<int,int> a, pair<int,int> b){
return {a.first+b.first,a.second+b.second};
}
pair<int,int> solve(int K){
for (int x = 0; x<=N; x++){
memo[N][x] = {0,0};
}
for (int x = N-1; x>=0; x--){
for (int o = 0; o<=N; o++){
memo[x][o] = memo[x+1][0]+make_pair(K+(range_len[x]>0),1);
if (o>range_len[x]) memo[x][o] = min(memo[x][o],memo[x+1][o-1]+make_pair(1,0));
else memo[x][o] = min(memo[x][o],memo[x+1][max(0LL,range_len[x]-1)]+make_pair((range_len[x]>0),0));
//printf("ans %lld %lld = %lld,%lld\n",x,o,memo[x][o]);
}
}
return memo[0][0];
}
main(){
scanf("%lld%lld%lld",&N,&D,&T);
for (int x = 0; x<N; x++){
int a;
scanf("%lld",&a);
range_len[x] = T-a+1;
if (range_len[x]<0) range_len[x] = 0;
if (x+range_len[x]>N) range_len[x] = N-x;
}
int a = -1;
int b = N;
while (a+1<b){
//printf("try %lld\n",(a+b)/2);
if (solve((a+b)/2).second>D){
a = (a+b)/2;
}
else b = (a+b)/2;
}
pair<int,int> res = solve(b);
//printf("b = %lld, res = %lld %lld\n",b,res);
printf("%lld",res.first-res.second*b-b*(D-res.second));
}
Compilation message
prison.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
28 | main(){
| ^~~~
prison.cpp: In function 'int main()':
prison.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%lld%lld%lld",&N,&D,&T);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
4556 KB |
Output is correct |
3 |
Correct |
10 ms |
4556 KB |
Output is correct |
4 |
Correct |
13 ms |
6220 KB |
Output is correct |
5 |
Correct |
13 ms |
6256 KB |
Output is correct |
6 |
Correct |
12 ms |
6220 KB |
Output is correct |
7 |
Correct |
15 ms |
6260 KB |
Output is correct |
8 |
Correct |
13 ms |
6220 KB |
Output is correct |
9 |
Correct |
15 ms |
6264 KB |
Output is correct |
10 |
Correct |
12 ms |
6220 KB |
Output is correct |
11 |
Correct |
12 ms |
6256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Runtime error |
77 ms |
8276 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
4556 KB |
Output is correct |
3 |
Correct |
10 ms |
4556 KB |
Output is correct |
4 |
Correct |
13 ms |
6220 KB |
Output is correct |
5 |
Correct |
13 ms |
6256 KB |
Output is correct |
6 |
Correct |
12 ms |
6220 KB |
Output is correct |
7 |
Correct |
15 ms |
6260 KB |
Output is correct |
8 |
Correct |
13 ms |
6220 KB |
Output is correct |
9 |
Correct |
15 ms |
6264 KB |
Output is correct |
10 |
Correct |
12 ms |
6220 KB |
Output is correct |
11 |
Correct |
12 ms |
6256 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
10 ms |
4556 KB |
Output is correct |
14 |
Correct |
8 ms |
4556 KB |
Output is correct |
15 |
Correct |
12 ms |
6220 KB |
Output is correct |
16 |
Correct |
16 ms |
6256 KB |
Output is correct |
17 |
Correct |
12 ms |
6260 KB |
Output is correct |
18 |
Correct |
13 ms |
6264 KB |
Output is correct |
19 |
Correct |
13 ms |
6220 KB |
Output is correct |
20 |
Correct |
12 ms |
6252 KB |
Output is correct |
21 |
Correct |
12 ms |
6220 KB |
Output is correct |
22 |
Correct |
16 ms |
6260 KB |
Output is correct |
23 |
Runtime error |
5 ms |
408 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Runtime error |
17 ms |
1600 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
4556 KB |
Output is correct |
3 |
Correct |
10 ms |
4556 KB |
Output is correct |
4 |
Correct |
13 ms |
6220 KB |
Output is correct |
5 |
Correct |
13 ms |
6256 KB |
Output is correct |
6 |
Correct |
12 ms |
6220 KB |
Output is correct |
7 |
Correct |
15 ms |
6260 KB |
Output is correct |
8 |
Correct |
13 ms |
6220 KB |
Output is correct |
9 |
Correct |
15 ms |
6264 KB |
Output is correct |
10 |
Correct |
12 ms |
6220 KB |
Output is correct |
11 |
Correct |
12 ms |
6256 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
10 ms |
4556 KB |
Output is correct |
14 |
Correct |
8 ms |
4556 KB |
Output is correct |
15 |
Correct |
12 ms |
6220 KB |
Output is correct |
16 |
Correct |
16 ms |
6256 KB |
Output is correct |
17 |
Correct |
12 ms |
6260 KB |
Output is correct |
18 |
Correct |
13 ms |
6264 KB |
Output is correct |
19 |
Correct |
13 ms |
6220 KB |
Output is correct |
20 |
Correct |
12 ms |
6252 KB |
Output is correct |
21 |
Correct |
12 ms |
6220 KB |
Output is correct |
22 |
Correct |
16 ms |
6260 KB |
Output is correct |
23 |
Runtime error |
5 ms |
408 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
4556 KB |
Output is correct |
3 |
Correct |
10 ms |
4556 KB |
Output is correct |
4 |
Correct |
13 ms |
6220 KB |
Output is correct |
5 |
Correct |
13 ms |
6256 KB |
Output is correct |
6 |
Correct |
12 ms |
6220 KB |
Output is correct |
7 |
Correct |
15 ms |
6260 KB |
Output is correct |
8 |
Correct |
13 ms |
6220 KB |
Output is correct |
9 |
Correct |
15 ms |
6264 KB |
Output is correct |
10 |
Correct |
12 ms |
6220 KB |
Output is correct |
11 |
Correct |
12 ms |
6256 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Runtime error |
77 ms |
8276 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |