// ./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,
ptr[MM];
ll A, B, C, T,
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;
// calculate "gain" amount
for (int i = 0; i < M; i++) {
ll 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);
gain[i][j] = nxt - cur;
cur = nxt;
}
}
// init
priority_queue<pair<ll, int>> pq;
ll ans = -1; // subtract station 1
for (int i = 0; i < M; i++) {
ans += gain[i][0];
if (K > 0)
pq.emplace(gain[i][++ptr[i]], i);
}
// greedy
for (int i = 0; i < K; i++) {
auto t = pq.top(); pq.pop();
ans += t.first;
if (ptr[t.second] < K)
pq.emplace(gain[t.second][++ptr[t.second]], t.second);
}
cout << ans << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
512 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
640 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
512 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
492 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2412 KB |
Output is correct |
| 20 |
Correct |
5 ms |
3052 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 23 |
Correct |
19 ms |
15596 KB |
Output is correct |
| 24 |
Correct |
3 ms |
5356 KB |
Output is correct |
| 25 |
Correct |
1 ms |
492 KB |
Output is correct |
| 26 |
Correct |
5 ms |
8300 KB |
Output is correct |
| 27 |
Correct |
4 ms |
6508 KB |
Output is correct |
| 28 |
Correct |
4 ms |
6508 KB |
Output is correct |
| 29 |
Correct |
6 ms |
4716 KB |
Output is correct |
| 30 |
Correct |
3 ms |
2156 KB |
Output is correct |
