Submission #524056

#	Time	Username	Problem	Language	Result	Execution time	Memory
524056		FireGhost1301	Semiexpress (JOI17_semiexpress)	C++11	100 / 100	6 ms	2504 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;

const int M = 3000 + 3;
int n, m, k;
int a, b, c;
long long t;
int s[M];
priority_queue<int> pq;

void solve() {
    cin >> n >> m >> k, k -= m;
    cin >> a >> b >> c;
    cin >> t;
    for (int i = 1; i <= m; ++i)
        cin >> s[i];
    int ans = 0;
    for (int i = 1; i < m; ++i) {
        int x = s[i], z = -1;
        long long tme = 1LL * b * (s[i] - 1);
        for (;;) {
            if (tme > t || x >= s[i + 1]) break;
            long long tmp = min((t - tme) / a + x, 1LL * s[i + 1] - 1);
            if (z != -1) pq.push(tmp - x + 1);
            else ans += tmp - x + 1;
            tme += 1LL * c * (tmp - x + 1), x = tmp + 1;
            if (++z >= k) break;
        }
    }
    while (!pq.empty() && k--)
        ans += pq.top(), pq.pop();
    if (1LL * b * (s[m] - 1) <= t) ++ans;
    cout << ans - 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52