제출 #1368831

#제출 시각아이디문제언어결과실행 시간메모리
1368831backer8002Tycho (BOI23_tycho)C++20
13 / 100
2097 ms2880 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<long> values(N + 2,LONG_MAX-D);
    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] + D <= c)
            continue;
        values[p.second] = min(c,values[p.second]);
        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();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…