#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
const int MAXN = 4010 ;
const int MAX = 2e6+10 ;
const int MAX4 = 150004 ;
using namespace std ;
int N , D , T , toGet, toFill = 1 ;
int t[MAX] ;
int dp[2][MAX];
int cost[MAXN][MAXN] ;
void solve(int l, int r, int optmin , int optmax )
{
if(l > r) return ;
int mid = (l+r)>>1 ;
int opt = optmin ;
dp[toFill][mid] = cost[opt][mid]+dp[toGet][opt-1] ;
for(int i = optmin+1 ; i <= min(mid,optmax) ; i++ )
{
int newCost = cost[i][mid] + dp[toGet][i-1] ;
if(newCost >= dp[toFill][mid]) continue ;
opt = i ;
dp[toFill][mid] = newCost ;
}
solve(l, mid-1, optmin, opt ) ;
solve(mid+1, r, opt, optmax );
}
void solve2()
{
vector<int> dpSuf(N+2,0) ;
vector<int> r(N+1,N+1) ;
for(int i = N ; i > 0 ; i-- )
{
r[i] = i+1 ;
while( r[i] <= N && t[i]+r[i]-i < t[r[i]] ) r[i] = r[ r[i] ] ;
int k = T-t[i]+i ;
dpSuf[i] = dpSuf[r[i]]+max(0,min( r[i]-1 , k )-i+1 ) ;
}
int s = t[1]+1 ;
int qtd = t[1] <= T ;
int ans = qtd+dpSuf[2] ;
for(int i = 2 ; i <= N ; i++ , s++ )
{
s = min(s, t[i] ) ;
qtd += s <= T ;
ans = min(ans, qtd+dpSuf[i+1]) ;
}
printf("%d\n" , ans ) ;
exit(0) ;
}
vector<int> p ;
int K ;
int tree[MAX4*4] ;
int lz[MAX4*4] ;
int m(int l, int r) { return (l+r)>>1 ; }
void refresh(int pos, int l, int r)
{
tree[pos] += lz[pos] ;
tree[pos] = min(tree[pos] , N+5) ;
if(l == r) return (void)(lz[pos] = 0 ) ;
lz[pos<<1] += lz[pos] ;
lz[pos<<1|1] += lz[pos] ;
lz[pos] = 0 ;
}
void clean(int pos, int l, int r, int beg, int en )
{
refresh(pos,l,r) ;
if(tree[pos] == N+5 || l > en || r < beg ) return ;
if( l== r )
{
tree[pos] = N+5 ;
return ;
}
clean(pos<<1 , l , m(l,r) , beg, en ) ;
clean(pos<<1|1 , m(l,r)+1, r , beg, en ) ;
tree[pos] = min(tree[pos<<1] , tree[pos<<1|1]) ;
}
void getMin(int pos, int l, int r, int beg, int en, int &cur )
{
refresh(pos,l,r) ;
if( l > en || r < beg) return ;
if( l >= beg && r <= en ) return (void)( cur = min(cur,tree[pos]) ) ;
getMin(pos<<1 , l , m(l,r ) , beg, en , cur ) ;
getMin(pos<<1|1 , m(l,r)+1, r, beg, en, cur ) ;
}
void updPoint(int pos, int l , int r, int x, int val )
{
refresh(pos,l,r) ;
tree[pos] = min(tree[pos] , val ) ;
if( l == r ) return ;
if( x <= m(l,r) ) updPoint(pos<<1 , l , m(l,r) , x , val ) ;
else updPoint(pos<<1|1 , m(l,r)+1 , r, x, val ) ;
}
void updInterval(int pos , int l, int r, int beg, int en )
{
refresh(pos,l,r) ;
if(l > en || r < beg) return ;
if( l >= beg && r <= en )
{
lz[pos]++ ;
refresh(pos,l,r) ;
return ;
}
updInterval(pos<<1 , l , m(l,r) , beg, en ) ;
updInterval(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
tree[pos] = min(tree[pos<<1] , tree[pos<<1|1]) ;
}
void solve4()
{
for(int i = 1 ; i <= N ; i++ )
{
p.push_back( t[i]-i ) ;
p.push_back( T-i ) ;
}
sort(all(p)) ;
p.erase(unique(all(p)) , p.end() ) ;
K = sz(p) ;
int s = T+1 ;
for(int i = 1 ; i <= N ; i++ , s++ )
{
s = min(s, t[i]) ;
dp[0][i] = dp[0][i-1]+(s <= T) ;
}
for(int j = 1 ; j <= D ; j++ , swap(toGet, toFill) )
{
clean(1,0,K-1, 0, K-1 ) ;
for(int i = 1 ; i <= N ; i++ )
{
int a = lower_bound(all(p), t[i]-i ) - p.begin() ;
int b = lower_bound(all(p), T-i ) - p.begin() ;
int cur = dp[toGet][i-1] ;
getMin( 1 , 0 , K-1 , a , K-1 , cur ) ;
clean(1,0,K-1, a, K-1) ;
updPoint(1,0,K-1, a, cur ) ;
updInterval(1,0,K-1, 0, b ) ;
dp[toFill][i] = N+5 ;
getMin(1,0,K-1, 0, K-1 , dp[toFill][i]) ;
}
}
printf("%d\n" , dp[toGet][N] ) ;
exit(0) ;
}
int main()
{
scanf("%d %d %d", &N, &D, &T ) ;
for(int i = 1 ; i <= N ; i++ ) scanf("%d", &t[i] ) ;
if( D <= 1 ) solve2() ;
if( D <= 15 ) solve4() ;
for(int i = 1 ; i <= N ; i++ )
{
int s = t[i]+1 ;
cost[i][i] = t[i] <= T ;
for(int j = i+1 ; j <= N ; j++ , s++ )
{
s = min(s, t[j] ) ;
cost[i][j] = cost[i][j-1]+(s <= T ) ;
}
}
for(int i = 1 ; i <= N ; i++ ) dp[0][i] = cost[1][i] ;
for(int i = 1 ; i <= D ; i++ , swap(toGet, toFill) )
{
for(int j = 1 ; j <= i ; j++ ) dp[toFill][j] = dp[toGet][j] ;
solve(i+1, N, i+1, N ) ;
}
printf("%d\n", dp[toGet][N] ) ;
}
Compilation message
prison.cpp: In function 'int main()':
prison.cpp:202:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
202 | scanf("%d %d %d", &N, &D, &T ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:203:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | for(int i = 1 ; i <= N ; i++ ) scanf("%d", &t[i] ) ;
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
316 KB |
Output is correct |
3 |
Correct |
3 ms |
2236 KB |
Output is correct |
4 |
Correct |
5 ms |
2848 KB |
Output is correct |
5 |
Correct |
4 ms |
2748 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
2748 KB |
Output is correct |
8 |
Correct |
7 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
2744 KB |
Output is correct |
10 |
Correct |
4 ms |
2764 KB |
Output is correct |
11 |
Correct |
4 ms |
2764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
80 ms |
7284 KB |
Output is correct |
3 |
Correct |
82 ms |
6424 KB |
Output is correct |
4 |
Correct |
74 ms |
6380 KB |
Output is correct |
5 |
Correct |
69 ms |
6368 KB |
Output is correct |
6 |
Correct |
71 ms |
6416 KB |
Output is correct |
7 |
Correct |
82 ms |
6400 KB |
Output is correct |
8 |
Correct |
77 ms |
6340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
316 KB |
Output is correct |
3 |
Correct |
3 ms |
2236 KB |
Output is correct |
4 |
Correct |
5 ms |
2848 KB |
Output is correct |
5 |
Correct |
4 ms |
2748 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
2748 KB |
Output is correct |
8 |
Correct |
7 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
2744 KB |
Output is correct |
10 |
Correct |
4 ms |
2764 KB |
Output is correct |
11 |
Correct |
4 ms |
2764 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
4 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
2252 KB |
Output is correct |
15 |
Correct |
3 ms |
2764 KB |
Output is correct |
16 |
Correct |
3 ms |
2764 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
2764 KB |
Output is correct |
19 |
Correct |
6 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
2764 KB |
Output is correct |
21 |
Correct |
4 ms |
2764 KB |
Output is correct |
22 |
Correct |
3 ms |
2764 KB |
Output is correct |
23 |
Correct |
54 ms |
45756 KB |
Output is correct |
24 |
Correct |
80 ms |
45776 KB |
Output is correct |
25 |
Correct |
90 ms |
45764 KB |
Output is correct |
26 |
Correct |
108 ms |
45776 KB |
Output is correct |
27 |
Correct |
136 ms |
45684 KB |
Output is correct |
28 |
Correct |
58 ms |
45764 KB |
Output is correct |
29 |
Correct |
52 ms |
45772 KB |
Output is correct |
30 |
Correct |
68 ms |
45656 KB |
Output is correct |
31 |
Correct |
96 ms |
45760 KB |
Output is correct |
32 |
Correct |
104 ms |
45760 KB |
Output is correct |
33 |
Correct |
92 ms |
45700 KB |
Output is correct |
34 |
Correct |
49 ms |
45636 KB |
Output is correct |
35 |
Correct |
131 ms |
45756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1933 ms |
6308 KB |
Output is correct |
3 |
Correct |
1894 ms |
4740 KB |
Output is correct |
4 |
Correct |
1504 ms |
4408 KB |
Output is correct |
5 |
Correct |
1775 ms |
4644 KB |
Output is correct |
6 |
Correct |
1745 ms |
4664 KB |
Output is correct |
7 |
Correct |
1865 ms |
4404 KB |
Output is correct |
8 |
Correct |
1846 ms |
4384 KB |
Output is correct |
9 |
Correct |
1918 ms |
6492 KB |
Output is correct |
10 |
Correct |
1668 ms |
4432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
316 KB |
Output is correct |
3 |
Correct |
3 ms |
2236 KB |
Output is correct |
4 |
Correct |
5 ms |
2848 KB |
Output is correct |
5 |
Correct |
4 ms |
2748 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
2748 KB |
Output is correct |
8 |
Correct |
7 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
2744 KB |
Output is correct |
10 |
Correct |
4 ms |
2764 KB |
Output is correct |
11 |
Correct |
4 ms |
2764 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
4 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
2252 KB |
Output is correct |
15 |
Correct |
3 ms |
2764 KB |
Output is correct |
16 |
Correct |
3 ms |
2764 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
2764 KB |
Output is correct |
19 |
Correct |
6 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
2764 KB |
Output is correct |
21 |
Correct |
4 ms |
2764 KB |
Output is correct |
22 |
Correct |
3 ms |
2764 KB |
Output is correct |
23 |
Correct |
54 ms |
45756 KB |
Output is correct |
24 |
Correct |
80 ms |
45776 KB |
Output is correct |
25 |
Correct |
90 ms |
45764 KB |
Output is correct |
26 |
Correct |
108 ms |
45776 KB |
Output is correct |
27 |
Correct |
136 ms |
45684 KB |
Output is correct |
28 |
Correct |
58 ms |
45764 KB |
Output is correct |
29 |
Correct |
52 ms |
45772 KB |
Output is correct |
30 |
Correct |
68 ms |
45656 KB |
Output is correct |
31 |
Correct |
96 ms |
45760 KB |
Output is correct |
32 |
Correct |
104 ms |
45760 KB |
Output is correct |
33 |
Correct |
92 ms |
45700 KB |
Output is correct |
34 |
Correct |
49 ms |
45636 KB |
Output is correct |
35 |
Correct |
131 ms |
45756 KB |
Output is correct |
36 |
Correct |
1 ms |
204 KB |
Output is correct |
37 |
Correct |
1933 ms |
6308 KB |
Output is correct |
38 |
Correct |
1894 ms |
4740 KB |
Output is correct |
39 |
Correct |
1504 ms |
4408 KB |
Output is correct |
40 |
Correct |
1775 ms |
4644 KB |
Output is correct |
41 |
Correct |
1745 ms |
4664 KB |
Output is correct |
42 |
Correct |
1865 ms |
4404 KB |
Output is correct |
43 |
Correct |
1846 ms |
4384 KB |
Output is correct |
44 |
Correct |
1918 ms |
6492 KB |
Output is correct |
45 |
Correct |
1668 ms |
4432 KB |
Output is correct |
46 |
Correct |
1 ms |
204 KB |
Output is correct |
47 |
Correct |
5 ms |
332 KB |
Output is correct |
48 |
Correct |
3 ms |
2252 KB |
Output is correct |
49 |
Correct |
3 ms |
2764 KB |
Output is correct |
50 |
Correct |
3 ms |
2744 KB |
Output is correct |
51 |
Correct |
2 ms |
332 KB |
Output is correct |
52 |
Correct |
3 ms |
2764 KB |
Output is correct |
53 |
Correct |
5 ms |
332 KB |
Output is correct |
54 |
Correct |
2 ms |
2744 KB |
Output is correct |
55 |
Correct |
3 ms |
2744 KB |
Output is correct |
56 |
Correct |
5 ms |
2764 KB |
Output is correct |
57 |
Correct |
52 ms |
45764 KB |
Output is correct |
58 |
Correct |
71 ms |
45860 KB |
Output is correct |
59 |
Correct |
92 ms |
45784 KB |
Output is correct |
60 |
Correct |
116 ms |
45776 KB |
Output is correct |
61 |
Correct |
123 ms |
45728 KB |
Output is correct |
62 |
Correct |
47 ms |
45772 KB |
Output is correct |
63 |
Correct |
48 ms |
45664 KB |
Output is correct |
64 |
Correct |
58 ms |
45760 KB |
Output is correct |
65 |
Correct |
83 ms |
45760 KB |
Output is correct |
66 |
Correct |
89 ms |
45732 KB |
Output is correct |
67 |
Correct |
92 ms |
45760 KB |
Output is correct |
68 |
Correct |
44 ms |
45752 KB |
Output is correct |
69 |
Correct |
127 ms |
45752 KB |
Output is correct |
70 |
Correct |
1 ms |
332 KB |
Output is correct |
71 |
Correct |
1974 ms |
6724 KB |
Output is correct |
72 |
Correct |
1939 ms |
4716 KB |
Output is correct |
73 |
Correct |
1492 ms |
4404 KB |
Output is correct |
74 |
Correct |
1683 ms |
4636 KB |
Output is correct |
75 |
Correct |
1819 ms |
4668 KB |
Output is correct |
76 |
Correct |
1774 ms |
4412 KB |
Output is correct |
77 |
Correct |
1787 ms |
4476 KB |
Output is correct |
78 |
Correct |
1863 ms |
6452 KB |
Output is correct |
79 |
Correct |
1652 ms |
4372 KB |
Output is correct |
80 |
Runtime error |
833 ms |
176228 KB |
Execution killed with signal 11 |
81 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
316 KB |
Output is correct |
3 |
Correct |
3 ms |
2236 KB |
Output is correct |
4 |
Correct |
5 ms |
2848 KB |
Output is correct |
5 |
Correct |
4 ms |
2748 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
2748 KB |
Output is correct |
8 |
Correct |
7 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
2744 KB |
Output is correct |
10 |
Correct |
4 ms |
2764 KB |
Output is correct |
11 |
Correct |
4 ms |
2764 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
80 ms |
7284 KB |
Output is correct |
14 |
Correct |
82 ms |
6424 KB |
Output is correct |
15 |
Correct |
74 ms |
6380 KB |
Output is correct |
16 |
Correct |
69 ms |
6368 KB |
Output is correct |
17 |
Correct |
71 ms |
6416 KB |
Output is correct |
18 |
Correct |
82 ms |
6400 KB |
Output is correct |
19 |
Correct |
77 ms |
6340 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
4 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
2252 KB |
Output is correct |
23 |
Correct |
3 ms |
2764 KB |
Output is correct |
24 |
Correct |
3 ms |
2764 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
3 ms |
2764 KB |
Output is correct |
27 |
Correct |
6 ms |
332 KB |
Output is correct |
28 |
Correct |
3 ms |
2764 KB |
Output is correct |
29 |
Correct |
4 ms |
2764 KB |
Output is correct |
30 |
Correct |
3 ms |
2764 KB |
Output is correct |
31 |
Correct |
54 ms |
45756 KB |
Output is correct |
32 |
Correct |
80 ms |
45776 KB |
Output is correct |
33 |
Correct |
90 ms |
45764 KB |
Output is correct |
34 |
Correct |
108 ms |
45776 KB |
Output is correct |
35 |
Correct |
136 ms |
45684 KB |
Output is correct |
36 |
Correct |
58 ms |
45764 KB |
Output is correct |
37 |
Correct |
52 ms |
45772 KB |
Output is correct |
38 |
Correct |
68 ms |
45656 KB |
Output is correct |
39 |
Correct |
96 ms |
45760 KB |
Output is correct |
40 |
Correct |
104 ms |
45760 KB |
Output is correct |
41 |
Correct |
92 ms |
45700 KB |
Output is correct |
42 |
Correct |
49 ms |
45636 KB |
Output is correct |
43 |
Correct |
131 ms |
45756 KB |
Output is correct |
44 |
Correct |
1 ms |
204 KB |
Output is correct |
45 |
Correct |
1933 ms |
6308 KB |
Output is correct |
46 |
Correct |
1894 ms |
4740 KB |
Output is correct |
47 |
Correct |
1504 ms |
4408 KB |
Output is correct |
48 |
Correct |
1775 ms |
4644 KB |
Output is correct |
49 |
Correct |
1745 ms |
4664 KB |
Output is correct |
50 |
Correct |
1865 ms |
4404 KB |
Output is correct |
51 |
Correct |
1846 ms |
4384 KB |
Output is correct |
52 |
Correct |
1918 ms |
6492 KB |
Output is correct |
53 |
Correct |
1668 ms |
4432 KB |
Output is correct |
54 |
Correct |
1 ms |
204 KB |
Output is correct |
55 |
Correct |
5 ms |
332 KB |
Output is correct |
56 |
Correct |
3 ms |
2252 KB |
Output is correct |
57 |
Correct |
3 ms |
2764 KB |
Output is correct |
58 |
Correct |
3 ms |
2744 KB |
Output is correct |
59 |
Correct |
2 ms |
332 KB |
Output is correct |
60 |
Correct |
3 ms |
2764 KB |
Output is correct |
61 |
Correct |
5 ms |
332 KB |
Output is correct |
62 |
Correct |
2 ms |
2744 KB |
Output is correct |
63 |
Correct |
3 ms |
2744 KB |
Output is correct |
64 |
Correct |
5 ms |
2764 KB |
Output is correct |
65 |
Correct |
52 ms |
45764 KB |
Output is correct |
66 |
Correct |
71 ms |
45860 KB |
Output is correct |
67 |
Correct |
92 ms |
45784 KB |
Output is correct |
68 |
Correct |
116 ms |
45776 KB |
Output is correct |
69 |
Correct |
123 ms |
45728 KB |
Output is correct |
70 |
Correct |
47 ms |
45772 KB |
Output is correct |
71 |
Correct |
48 ms |
45664 KB |
Output is correct |
72 |
Correct |
58 ms |
45760 KB |
Output is correct |
73 |
Correct |
83 ms |
45760 KB |
Output is correct |
74 |
Correct |
89 ms |
45732 KB |
Output is correct |
75 |
Correct |
92 ms |
45760 KB |
Output is correct |
76 |
Correct |
44 ms |
45752 KB |
Output is correct |
77 |
Correct |
127 ms |
45752 KB |
Output is correct |
78 |
Correct |
1 ms |
332 KB |
Output is correct |
79 |
Correct |
1974 ms |
6724 KB |
Output is correct |
80 |
Correct |
1939 ms |
4716 KB |
Output is correct |
81 |
Correct |
1492 ms |
4404 KB |
Output is correct |
82 |
Correct |
1683 ms |
4636 KB |
Output is correct |
83 |
Correct |
1819 ms |
4668 KB |
Output is correct |
84 |
Correct |
1774 ms |
4412 KB |
Output is correct |
85 |
Correct |
1787 ms |
4476 KB |
Output is correct |
86 |
Correct |
1863 ms |
6452 KB |
Output is correct |
87 |
Correct |
1652 ms |
4372 KB |
Output is correct |
88 |
Runtime error |
833 ms |
176228 KB |
Execution killed with signal 11 |
89 |
Halted |
0 ms |
0 KB |
- |