Submission #1368839

#TimeUsernameProblemLanguageResultExecution timeMemory
1368839backer8002Tycho (BOI23_tycho)C++20
5 / 100
2095 ms327680 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    long B, P, D, N;
    cin >> B >> P >> D >> N;

    vector<long> places(N + 2);
    places[0] = 0, places.back() = B;
    for (int i = 0; i < N; i++)
        cin >> places[i + 1];
    vector values(N + 2,make_pair(LONG_MAX,LONG_MAX));
    priority_queue<pair<long, pair<long, int> >, vector<pair<long, pair<long, int> > >, greater<> > pq;
    pq.emplace(places[1] + (places[1] - 1) / P * D, make_pair(places[1], 1));
    while (!pq.empty()) {
        auto [c,p] = pq.top();
        pq.pop();
        if (values[p.second].first <= c and p.first - values[p.second].second > P)
            continue;
        if (values[p.second].first > c) {
            values[p.second].first = c;
            values[p.second].second = p.first;
        } else if (values[p.second].first == c)
            values[p.second].second = min(values[p.second].second,p.first);

        if (p.second == N + 1)
            break;
        const long dist = places[p.second + 1] - places[p.second];
        const long cost1 = c + (dist + p.first % P - 1) / P * D + dist;
        pq.emplace(cost1, make_pair(p.first + dist, p.second + 1));
        if (const long cost2 = c + (dist - 1) / P * D + P - p.first % P + dist; cost2 <= cost1 + P - p.first % P)
            pq.emplace(cost2,make_pair(p.first + P - p.first % P + dist, p.second + 1));
    }
    cout << values.back().first;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...