Submission #1180123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180123		niepamietamhasla	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	0 ms	572 KiB

semiexpress

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

ll w = 0;
ll A, B, C;

struct d{
    ll nxtC;
    ll currB;
    ll kosztdo;
    ll iledodatkowych;
};

vector<ll> M;
ll T;

struct comp{
    bool operator()(const d &d1, const d &d2){
        if(d1.iledodatkowych != d2.iledodatkowych){
            return d1.iledodatkowych < d2.iledodatkowych;
        }
        return false;
    }
};

priority_queue<d, vector<d>, comp> pq;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    ll x;
    cin >> A >> B >> C;
    cin >> T;
    for(ll i = 0; i < m; ++i){
        cin >> x;
        M.push_back(x);
    }
    if(T - (M[m-1] - 1) * B >= 0) w++;
    for(ll i = 0; i < m-1; ++i){
        ll ind = M[i];
        //cout << T - (ind - 1) * B << " T\n";
        if(T - (ind - 1) * B < 0) continue;
        else if(T - (ind - 1) * B == 0){
            w++;
            continue;
        }
        ll nxt = (T - (ind - 1) * B) / A + ind + 1;
        //cout << w << " wprzed\n";
        w += min(nxt - ind, M[i+1] - ind);
        //cout << w << " wpo\n";
        if(nxt >= M[i+1]){
            continue;
        }
        ll w1 = (T - (ind - 1) * B - (nxt - ind) * C) / A + 1;
        w1 = min(w1, M[i+1] - nxt);
        if((T - (ind - 1) * B - (nxt - ind) * C) == 0){
            w1 = 1;
        }
        if((T - (ind - 1) * B - (nxt - ind) * C) < 0) continue;
        //cout << i << " " << M[i+1] << " " << nxt << " " << (ind - 1) * B + (nxt - ind) * C << " " << w1 << " dodawac\n";
        pq.push({M[i+1], nxt, (ind - 1) * B + (nxt - ind) * C, w1});
    }
    k -= m;
    //cout << w << " po base\n";
    while(k > 0 and pq.size() > 0){
        auto u = pq.top();
        pq.pop();

        //cout << u.currB << " " << u.nxtC << " " << u.kosztdo << " " << u.iledodatkowych << " " << k << " u\n";
        w += u.iledodatkowych;
        ll ind = u.currB;
        ll nxt = ind + u.iledodatkowych;
        k--;
        if(nxt >= u.nxtC){
            continue;
        }
        ll w1 = (T - u.kosztdo - (nxt - ind) * C) / A + 1;
        w1 = min(w1, u.nxtC - nxt);
        if((T - u.kosztdo - (nxt - ind) * C) < 0) continue;
        if((T - u.kosztdo - (nxt - ind) * C)  == 0) w1 = 1;

        //cout << u.nxtC << " " << nxt << " " << u.kosztdo + (nxt - ind) * C << " " << w1 << " dod\n";
        pq.push({u.nxtC, nxt, u.kosztdo + (nxt - ind) * C, w1});
    }
    cout << w - 1 << "\n";
    return 0;
}

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