Submission #1304634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304634		polishprogrammer	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	2 ms	584 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lld long double

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, k, a, b, c, t;
    cin >> n >> m >> k >> a >> b >> c >> t;
    vector<ll> arr(m);
    for (ll i = 0; i < m; i++) cin >> arr[i];
    ll nk = k - m;
    priority_queue<pair<pair<ll, ll>, pair<ll, ll>>> pq; // {{zysk, miejsce}, {pop, nas}}
    ll wyn = 0;
    for (ll i = 1; i < m; i++) {
        ll pop = arr[i - 1], nas = arr[i], dl = nas - pop, czas = (pop - 1) * b;
        if (czas > t) break;
        ll poz = t - czas, d = poz / a, dod = min(d, dl - 1);
        wyn += dod;
        if (d < dl - 1) {
            ll miejsce = pop + d + 1;
            czas += (miejsce - pop) * c;
            if (czas <= t) {
                ll d2 = (t - czas) / a, zysk = min(nas - miejsce, d2 + 1);
                pq.push({{zysk, miejsce}, {pop, nas}});
            }
        }
        if ((nas - 1) * b <= t) wyn++;
    }
    while (nk > 0 && !pq.empty()) {
        pair<pair<int, int>, pair<int, int>> p = pq.top();
        pq.pop();
        ll zysk = p.fi.fi, miejsce = p.fi.se, pop = p.se.fi, nas = p.se.se;
        wyn += zysk;
        miejsce += zysk;
        if (miejsce < nas) {
            ll czas = (pop - 1) * b + (miejsce - pop) * c;
            if (czas <= t) {
                ll d2 = (t - czas) / a;
                pq.push({{min(nas - miejsce, d2 + 1), miejsce}, {pop, nas}});
            }
        }
        nk--;
    }
    cout << wyn << endl;
}

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