Submission #1156197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156197		mocha	Semiexpress (JOI17_semiexpress)	C++20	0 / 100	0 ms	324 KiB

semiexpress

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mx = 4e5+5;

int n, m, k;
int A, B, C;
int T;
int a[mx];
int ans;

struct Nd {
    int len, vl, val;

    friend bool operator<(Nd a, Nd b) {
        return a.val < b.val;
    }

    void cnt_cost() {
        int mn = vl;
        if (mn > T) {
            val = 0;
            return;
        }
        val = min(len, (T-mn)/A+1);
    }
};

signed main() {
    cin >> n >> m >> k; k-=m;
    cin >> A >> B >> C;
    cin >> T;
    for (int i=1;i<=m;i++) cin >> a[i];
    priority_queue<Nd> pq;
    for (int i=1;i<m;i++) {
        int t = a[i] * B;
        if (t>T) break;
        int r = (T-t) / A;
        if (a[i] + r >= a[i+1]) {
            ans += a[i+1] - a[i];
            continue;
        }
        ans += r + 1;
        Nd nd = {a[i+1]-a[i]-r-1, t + C * (r+1), 0};
        nd.cnt_cost();
        pq.push(nd);
    }
    if (B*n <= T) ans++;
    while (k-- and pq.size()) {
        auto nd = pq.top(); pq.pop();
        if (nd.val==0) break;
        ans += nd.val;
        nd.vl += C * nd.val;
        nd.len -= nd.val;
        nd.cnt_cost();
        pq.push(nd);
    }
    cout << (ans-1<0?0:ans-1) << "\n";
}

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