Submission #583693

#	Time	Username	Problem	Language	Result	Execution time	Memory
583693		Jomnoi	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	7 ms	4556 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52