#include <bits/stdc++.h>
using namespace std ;
const int MAX = 4000 + 10 ;
int arr[MAX] ;
int n , m , t ;
vector< pair<int , int> >vp ;
int st[MAX] ;
int cost[MAX][MAX] ;
int dp[MAX][MAX] ;
int solve()
{
int sz = (int)(vp.size()) - 1 ;
for(int i = 1 ; i <= sz ; ++i)
{
int curtim = 2e9 , sum = 0 ;
for(int j = i ; j <= sz ; ++j)
{
curtim = min(curtim , arr[vp[j].second-1]+1) ;
sum += min(t - curtim + 1 , vp[j].first) ;
cost[i][j] = sum ;
if(j+1 <= sz)
curtim += vp[j+1].second - vp[j].second ;
}
}
for(int i = 1 ; i <= sz ; ++i)
dp[i][0] = cost[1][i] ;
for(int j = 1 ; j <= m ; ++j)
{
for(int i = 1 ; i <= sz ; ++i)
{
dp[i][j] = 1e9 ;
for(int k = i ; k >= 1 ; --k) //put mattress at k
dp[i][j] = min(dp[i][j] , dp[k-1][j-1] + cost[k+1][i]) ;
}
}
return dp[sz][m] ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>m>>t ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
arr[0] = 1e9 + 10 ;
vp.emplace_back(0 , 1e9+10) ;
int ans = 0 , last = -1 , cnt = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
if(arr[i] <= t)
{
arr[i] = min(arr[i] , arr[i-1] + 1) ;
if(cnt && last != -1)
vp.emplace_back(cnt , last+1) ;
ans++ , last = i , cnt = 0 ;
}
else
cnt++ ;
}
if(cnt && last != -1)
vp.emplace_back(cnt , last+1) , cnt = 0 ;
ans += solve() ;
return cout<<ans<<"\n" , 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1236 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
2 ms |
1352 KB |
Output is correct |
6 |
Correct |
1 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
988 KB |
Output is correct |
8 |
Correct |
1 ms |
1364 KB |
Output is correct |
9 |
Correct |
1 ms |
1296 KB |
Output is correct |
10 |
Correct |
1 ms |
1224 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1236 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
2 ms |
1352 KB |
Output is correct |
6 |
Correct |
1 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
988 KB |
Output is correct |
8 |
Correct |
1 ms |
1364 KB |
Output is correct |
9 |
Correct |
1 ms |
1296 KB |
Output is correct |
10 |
Correct |
1 ms |
1224 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
0 ms |
328 KB |
Output is correct |
13 |
Correct |
1 ms |
1224 KB |
Output is correct |
14 |
Correct |
1 ms |
1240 KB |
Output is correct |
15 |
Correct |
2 ms |
1364 KB |
Output is correct |
16 |
Correct |
2 ms |
1356 KB |
Output is correct |
17 |
Correct |
1 ms |
1100 KB |
Output is correct |
18 |
Correct |
1 ms |
980 KB |
Output is correct |
19 |
Correct |
1 ms |
1364 KB |
Output is correct |
20 |
Correct |
1 ms |
1364 KB |
Output is correct |
21 |
Correct |
2 ms |
1236 KB |
Output is correct |
22 |
Correct |
2 ms |
1492 KB |
Output is correct |
23 |
Correct |
97 ms |
9964 KB |
Output is correct |
24 |
Correct |
297 ms |
11088 KB |
Output is correct |
25 |
Correct |
364 ms |
10636 KB |
Output is correct |
26 |
Correct |
555 ms |
11836 KB |
Output is correct |
27 |
Correct |
454 ms |
11344 KB |
Output is correct |
28 |
Correct |
91 ms |
10576 KB |
Output is correct |
29 |
Correct |
74 ms |
9780 KB |
Output is correct |
30 |
Correct |
119 ms |
9872 KB |
Output is correct |
31 |
Correct |
273 ms |
10048 KB |
Output is correct |
32 |
Correct |
1376 ms |
19864 KB |
Output is correct |
33 |
Correct |
1291 ms |
19984 KB |
Output is correct |
34 |
Correct |
35 ms |
6880 KB |
Output is correct |
35 |
Correct |
278 ms |
9724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1236 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
2 ms |
1352 KB |
Output is correct |
6 |
Correct |
1 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
988 KB |
Output is correct |
8 |
Correct |
1 ms |
1364 KB |
Output is correct |
9 |
Correct |
1 ms |
1296 KB |
Output is correct |
10 |
Correct |
1 ms |
1224 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
0 ms |
328 KB |
Output is correct |
13 |
Correct |
1 ms |
1224 KB |
Output is correct |
14 |
Correct |
1 ms |
1240 KB |
Output is correct |
15 |
Correct |
2 ms |
1364 KB |
Output is correct |
16 |
Correct |
2 ms |
1356 KB |
Output is correct |
17 |
Correct |
1 ms |
1100 KB |
Output is correct |
18 |
Correct |
1 ms |
980 KB |
Output is correct |
19 |
Correct |
1 ms |
1364 KB |
Output is correct |
20 |
Correct |
1 ms |
1364 KB |
Output is correct |
21 |
Correct |
2 ms |
1236 KB |
Output is correct |
22 |
Correct |
2 ms |
1492 KB |
Output is correct |
23 |
Correct |
97 ms |
9964 KB |
Output is correct |
24 |
Correct |
297 ms |
11088 KB |
Output is correct |
25 |
Correct |
364 ms |
10636 KB |
Output is correct |
26 |
Correct |
555 ms |
11836 KB |
Output is correct |
27 |
Correct |
454 ms |
11344 KB |
Output is correct |
28 |
Correct |
91 ms |
10576 KB |
Output is correct |
29 |
Correct |
74 ms |
9780 KB |
Output is correct |
30 |
Correct |
119 ms |
9872 KB |
Output is correct |
31 |
Correct |
273 ms |
10048 KB |
Output is correct |
32 |
Correct |
1376 ms |
19864 KB |
Output is correct |
33 |
Correct |
1291 ms |
19984 KB |
Output is correct |
34 |
Correct |
35 ms |
6880 KB |
Output is correct |
35 |
Correct |
278 ms |
9724 KB |
Output is correct |
36 |
Correct |
0 ms |
340 KB |
Output is correct |
37 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1236 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
2 ms |
1352 KB |
Output is correct |
6 |
Correct |
1 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
988 KB |
Output is correct |
8 |
Correct |
1 ms |
1364 KB |
Output is correct |
9 |
Correct |
1 ms |
1296 KB |
Output is correct |
10 |
Correct |
1 ms |
1224 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |