Submission #1179941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179941		M_W_13	Semiexpress (JOI17_semiexpress)	C++20	0 / 100	0 ms	320 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
ll tim;
ll A, B, C;

struct trojka {
    ll x;
    ll t;
    ll ogr;
};

class compare {
    public:
        bool operator() (trojka a, trojka b) {
            return (min(max(0ll, (tim - a.t)/A), a.ogr) < min(max(0ll, (tim - b.t)/A), b.ogr));
        }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    cin >> A >> B >> C;
    cin >> tim;
    cout << ((tim - 81ll * B)/C) << '\n';
    ll T[m];
    rep(i, m) {
        cin >> T[i];
    }
    ll ans = 0;
    priority_queue<trojka, vector<trojka>, compare> pq;
    rep(i, m - 1) {
        ll dl = (T[i] - 1ll) * B;
        ll dokad = min(T[i + 1] - 1, T[i] + max(0ll, (tim - dl)/A));
        if (dl <= tim) {
            // cout << "T = " << T[i] << '\n';
            ans += (dokad - T[i] + 1);
        }
        pq.push({dokad + 1, dl + C * (dokad + 1 - T[i]), T[i + 1] - (dokad + 1)});
    }
    // cout << "ans = " << ans << '\n';
    while (m < k) {
        if (pq.empty()) {
            break;
        }
        trojka tr = pq.top();
        pq.pop();
        // cout << "x = " << tr.x << " time = " << tr.t << " ogr = " << tr.ogr << '\n';
        if (tr.ogr == 0 || tr.t > tim) {
            continue;
        }
        ll dl = tr.t;
        ll nekst = tr.x + tr.ogr;
        ll dokad = min(nekst - 1, tr.x + max(0ll, (tim - dl)/A));
        // cout << "dokad = " << dokad << '\n';
        // cout << ((tim - dl)/C) << '\n';
        ans += (dokad - tr.x + 1);
        pq.push({dokad + 1, dl + C * (dokad + 1 - tr.x), nekst - (dokad + 1)});
        m++;
    }
    if (((n - 1) * B) > tim) {
        ans--;
    }
    cout << ans << '\n';
    return 0;
}

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