oj.uz

Submission #583693

# Submission time Handle Problem Language Result Execution time Memory
583693 2022-06-26T05:29:44 Z Jomnoi Semiexpress (JOI17_semiexpress) C++17
100 / 100
 7 ms 4556 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 3005;

long long S[MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, M, K;
    long long A, B, C;
    long long T;
    cin >> N >> M >> K;
    cin >> A >> B >> C;
    cin >> T;

    K -= M;

    for(int i = 1; i <= M; i++) {
        cin >> S[i];
    }
    S[M + 1] = N + 1;

    long long ans = -1;
    long long cost, now, nxt;
    priority_queue <long long> pq;
    for(int i = 1; i <= M; i++) {
        cost = B * (S[i] - 1);
        if(cost > T) {
            break;
        }

        nxt = min(S[i] + (T - cost) / A + 1, S[i + 1]);

        ans += nxt - S[i];

        int cnt = K;
        while(nxt < S[i + 1] and cnt--) {
            now = nxt;
            cost = B * (S[i] - 1) + C * (now - S[i]);
            if(cost > T) {
                break;
            }

            nxt = min(now + (T - cost) / A + 1, S[i + 1]);

            pq.push(nxt - now);
        }
    }

    while(!pq.empty() and K--) {
        ans += pq.top();
        pq.pop();
    }
    cout << ans;
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 7 ms 4556 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 7 ms 4556 KB Output is correct
30 Correct 4 ms 2512 KB Output is correct