Submission #583693

#TimeUsernameProblemLanguageResultExecution timeMemory
583693JomnoiSemiexpress (JOI17_semiexpress)C++17
100 / 100
7 ms4556 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...