Submission #749935

#	Time	Username	Problem	Language	Result	Execution time	Memory
749935		Pring	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	2 ms	436 KiB

semiexpress

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

#define int long long
typedef pair<int, int> pii;

const int MXN = 3005;
int n, m, k, A, B, C, T, a[MXN], ans;

struct P {
    int now, r, x, l;
    P() {
        now = 0;
        r = 0;
        x = 0;
        l = 0;
    }
    void calc() {
        if (x < 0) l = 0;
        else l = min(r, x / A + 1);
    }
    void push() {
        ans += l;
        r -= l;
        x -= C * l;
        calc();
    }
} p[MXN];

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> m >> k >> A >> B >> C >> T;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        a[i]--;
    }
    a[m] = n;
    for (int i = 0; i < m; i++) {
        p[i].now = 0;
        p[i].r = a[i + 1] - a[i];
        p[i].x = T - a[i] * B;
        p[i].calc();
        // cout << p[i].now << ' ' << p[i].r << ' ' << p[i].x << ' ' << p[i].l << endl;
        p[i].push();
    }
    // cout << endl;
    // cout << ans << endl;
    // for (int i = 0; i < m; i++) cout << p[i].now << ' ' << p[i].r << ' ' << p[i].x << ' ' << p[i].l << endl;
    // cout << endl;
    for (int i = m; i < k; i++) {
        int bigid = 0;
        for (int j = 1; j < m; j++) {
            if (p[bigid].l < p[j].l) bigid = j;
        }
        p[bigid].push();
        // for (int j = 0; j < m; j++) cout << p[j].now << ' ' << p[j].r << ' ' << p[j].x << ' ' << p[j].l << endl;
        // cout << endl;
    }
    cout << ans - 1 << endl;
    return 0;
}

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