Submission #1156206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156206		mocha	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	1 ms	328 KiB

semiexpress

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

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

struct node {
    int l, r, val;

    friend bool operator<(node a, node b) {
        return a.l == b.l ? a.r == b.r ? a.val > b.val : a.r < b.r : a.l < b.l;
    }
};

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];
    int t = 0;
    int pre = 1;
    priority_queue<Nd> pq;
    for (int i=1;i<m;i++) {
        t += (a[i]-pre) * B;
        pre = a[i];
        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();
        if (nd.val>0) pq.push(nd);
    }
    if (B*(n-1) <= T) ans++;
    while (k-- and pq.size()) {
        auto nd = pq.top(); pq.pop();
        ans += nd.val;
        nd.vl += C * nd.val;
        nd.len -= nd.val;
        nd.cnt_cost();
        if (nd.val > 0) {
            pq.push(nd);
        }
    }
    cout << (ans-1<0?0:ans-1) << "\n";
}

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