Submission #717946

#	Time	Username	Problem	Language	Result	Execution time	Memory
717946		thimote75	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	1 ms	300 KiB

semiexpress

#include <bits/stdc++.h>
#define num long long
#define ndt pair<num, int>

using namespace std;

num A, B, C;
num result = -1;

vector<num> dx_array;
vector<num> dt_array;
priority_queue<ndt> ndt_queue;

ndt compute (num dx, num dt, int id) {
    double time = dt;
    if (dx < 0 || dt < 0) return { 0, id };

    return { min(dx, (num) (floor(time / A) + 1)), id };
}
ndt compute (int id) {
    return compute(dx_array[id], dt_array[id], id);
}
void update (ndt repr) {
    int target = repr.second;
    num count  = repr.first;

    result += count;

    dx_array[target] -= count;
    dt_array[target] -= C * count;

    ndt_queue.push(compute(target));
}

int main () {
    int N, M, K;
    cin >> N >> M >> K;
    cin >> A >> B >> C;
    K -= M;

    num T;
    cin >> T;

    dx_array.resize(M - 1);
    dt_array.resize(M - 1);

    int last;
    cin >> last;

    num delta_t = 0;
    for (int id = 1; id < M; id ++) {
        int x; cin >> x;

        dx_array[id - 1] = x - last;
        dt_array[id - 1] = T - (last - 1) * B;

        delta_t ++;
        last = x;

        update(compute(id - 1));
    }

    if (N * C <= T) result ++;

    while (ndt_queue.size() != 0 && K > 0) {
        ndt m = ndt_queue.top(); ndt_queue.pop();
        update(m);

        K --;
    }

    cout << result;
}

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