Submission #1199478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199478		efishel	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	40 ms	25116 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll INF = ll(1E18)+16;

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m, k;
    cin >> n >> m >> k;
    k -= m;
    ll a, b, c;
    cin >> a >> b >> c;
    ll T;
    cin >> T;
    vll ve(m);
    for (ll &i : ve) cin >> i, i--;
    auto fincs = [&](ll i, ll len) {
        ll tLeft = T - i*b;
        vll ans(k+1, 0);
        if (tLeft < 0) return ans;
        // ans[j] = number of extra cities reached using j semi-express stops
        ans[0] = min(tLeft/a, len);
        for (ll j = 1; j <= k; j++) {
            ll tLeftLeft = tLeft - (ans[j-1]+1)*c;
            if (tLeftLeft < 0) { ans[j] = ans[j-1]; continue; }
            ans[j] = min(ans[j-1] + 1 + tLeftLeft/a, len);
        }
        for (ll j = k; j > 0; j--)
            ans[j] -= ans[j-1];
        return ans;
    };
    vector <vll> mat;
    ll last = 0;
    ll ans = 0;
    vll th;
    for (ll i : ve) {
        if (i == 0) continue;
        mat.push_back(fincs(last, i-last-1));
        ans += mat.back()[0];
        if (i*b <= T) ans++;
        mat.back().erase(mat.back().begin());
        for (ll i : mat.back()) th.push_back(i);
        // cerr << last << "---" << i << '\n';
        // for (ll j : mat.back()) cerr << setw(2) << j << ' ';
        // cerr << '\n';
        last = i;
    }
    sort(th.rbegin(), th.rend());
    for (ll i = 0; i < k; i++) {
        ans += th[i];
    }
    cout << ans << '\n';
    // vll dp(k+1, 0), nDp(k+1, 0);
    // for (ll i : ve) {
    //     vll th = fincs(last, i-last-1);
    //     for (ll j = 0; j <= k; j++) {
    //         ;
    //     }
    // }
    return 0;
}

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