// ./joi-2017-final-p2----semiexpress.yml
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f;
const int MM = 3011;
int N, M, K;
ll A, B, C, T,
dp[MM][MM], gain[MM][MM], S[MM];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K >> A >> B >> C >> T;
for (int i = 0; i < M; i++) cin >> S[i];
S[M] = N+1;
K -= M;
for (int i = 0; i < M; i++) {
ll add = 0, cur = S[i]-1;
for (int j = 0; j <= K; j++) {
ll init = (S[i]-1)*B + (cur+1-S[i])*C;
if (init > T) break;
ll nxt = min(cur+1 + (T-init) / A, S[i+1]-1);
// printf("i=%d j=%d init=%lld cur=%lld nxt=%lld add=%lld\n", i,j,init,cur,nxt,add+nxt-cur);
add += nxt - cur;
cur = nxt;
gain[i][j] = add;
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j <= K; j++) {
// printf("i=%d j=%d dp=%lld\n", i,j,dp[i][j]);
for (int k = 0; k <= K-j; k++) {
dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + gain[i][k]);
// printf("to i=%d j=%d k=%d gain=%lld\n", i+1,j+k,k,gain[i][k]);
}
}
}
// subtract station 1
cout << dp[M][K]-1 << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
620 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
532 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
620 KB |
Output is correct |
| 17 |
Correct |
1 ms |
492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
620 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
532 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
620 KB |
Output is correct |
| 17 |
Correct |
1 ms |
492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
620 KB |
Output is correct |
| 19 |
Correct |
171 ms |
13548 KB |
Output is correct |
| 20 |
Correct |
838 ms |
20004 KB |
Output is correct |
| 21 |
Correct |
7 ms |
6252 KB |
Output is correct |
| 22 |
Correct |
18 ms |
9196 KB |
Output is correct |
| 23 |
Correct |
386 ms |
30976 KB |
Output is correct |
| 24 |
Correct |
7 ms |
10476 KB |
Output is correct |
| 25 |
Correct |
4 ms |
4460 KB |
Output is correct |
| 26 |
Correct |
10 ms |
16364 KB |
Output is correct |
| 27 |
Correct |
8 ms |
12524 KB |
Output is correct |
| 28 |
Correct |
8 ms |
12780 KB |
Output is correct |
| 29 |
Correct |
102 ms |
9196 KB |
Output is correct |
| 30 |
Correct |
188 ms |
4204 KB |
Output is correct |
