Submission #1304625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304625		polishprogrammer	Semiexpress (JOI17_semiexpress)	C++20	0 / 100	1 ms	568 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;
    k -= m;
    ll wyn = -1;
    cin >> a >> b >> c;
    cin >> t;
    vector<ll> arr(m);
    for (ll i = 0; i < m; i++) cin >> arr[i];
    priority_queue<pair<pair<ll, ll>, pair<ll, ll>>> pq;
    for (ll i = 1; i < m; i++) {
        ll czas = (arr[i - 1] - 1) * b, ak = min(arr[i], (t - czas) / a + arr[i - 1] + 1);
        //cout << "przyjazd do " << arr[i - 1] << " czas przyjazdu " << czas << " nowa stacja: " << ak << endl;
        if (czas > t) break;
        wyn += ak - arr[i - 1];
        if (ak < arr[i]) {
            czas += (ak - arr[i - 1]) * c;
            if (czas <= t) {
                ll zysk = min(arr[i] - ak, (t - czas) / a + 1);
                //cout << zysk << " " << (t - czas - (ak - arr[i - 1]) * c) / a + 1 << " " << ak << endl;
                pq.push({{zysk, ak}, {arr[i - 1], arr[i]}});
            }
            else wyn--; // nie da dojechać sie do ak w czasie
        }
    }
    if (b * (n - 1) <= t) wyn++;
    while (k-- and !pq.empty()) {
        pair<pair<ll, ll>, pair<ll, ll>> 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) {
                zysk = min(nas - miejsce, (t - czas) / a + 1);
                pq.push({{zysk, miejsce}, {pop, nas}});
            }
        }
    }
    cout << wyn << endl;
}

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