Submission #396916

#	Time	Username	Problem	Language	Result	Execution time	Memory
396916		timmyfeng	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	15 ms	4548 KiB

semiexpress

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

const int N = 3000;

long long express[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, k, a, b, c, t;
    cin >> n >> m >> k >> a >> b >> c >> t;

    for (int i = 0; i < m; ++i) {
        cin >> express[i];
        --express[i];
    }

    long long ans = -1;
    vector<long long> semiexpress;
    for (int i = 0; i < m - 1; ++i) {
        long long x = express[i];
        for (int j = 0; j <= k - m; ++j) {
            if (x == express[i + 1] || b * express[i] + c * (x - express[i]) > t) {
                break;
            }

            long long remain = t - b * express[i] - c * (x - express[i]);
            long long y = min(express[i + 1], x + remain / a + 1);
            if (x == express[i]) {
                ans += y - x;
            } else {
                semiexpress.push_back(y - x);
            }
            x = y;
        }
    }
    ans += b * express[m - 1] <= t;

    sort(semiexpress.rbegin(), semiexpress.rend());
    for (int i = 0; i < k - m && i < (int) semiexpress.size(); ++i) {
        ans += semiexpress[i];
    }

    cout << ans << "\n";
}

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