제출 #1332494

#제출 시각아이디문제언어결과실행 시간메모리
1332494ee23b179_cpLong Distance Coach (JOI17_coach)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

const long long INF = 2e18;

struct Passenger {
    long long d, c;
    bool operator<(const Passenger& o) const {
        return d < o.d;
    }
};

struct Line {
    long long m, c;
    long long eval(long long x) {
        return m * x + c;
    }
};

struct CHT {
    deque<Line> dq;
    
    bool bad(Line l1, Line l2, Line l3) {
        return (__int128)(l3.c - l1.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l1.m - l3.m);
    }
    
    void add(long long m, long long c) {
        Line l = {m, c};
        while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq.back(), l)) {
            dq.pop_back();
        }
        dq.push_back(l);
    }
    
    long long query(long long x) {
        if (dq.empty()) return INF;
        while (dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x)) {
            dq.pop_front();
        }
        return dq[0].eval(x);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long X, N, M, W, T;
    if (!(cin >> X >> N >> M >> W >> T)) return 0;

    vector<long long> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    S.push_back(X);
    N++;

    vector<Passenger> P(M);
    for (int i = 0; i < M; i++) {
        cin >> P[i].d >> P[i].c;
    }

    sort(P.begin(), P.end());

    vector<long long> prefC(M + 1, 0);
    for (int i = 0; i < M; i++) {
        prefC[i + 1] = prefC[i] + P[i].c;
    }

    vector<long long> dp(M + 1, INF);
    dp[0] = 0;

    CHT cht;
    
    long long base_water = X / T + 1;
    long long current_water = base_water * W;

    for (int i = 1; i <= M; i++) {
        long long current_cost = current_water + prefC[i];
        dp[i] = min(dp[i], current_cost);
    }

    sort(S.begin(), S.end());
    
    vector<long long> W_cost(M + 1, 0);
    
    for (int i = 0; i < N; i++) {
        long long rem = S[i] % T;
        long long div = S[i] / T;
        
        int idx = upper_bound(P.begin(), P.end(), Passenger{rem, 0}) - P.begin();
        
        long long val = div * W;
        W_cost[idx] += val;
    }

    long long acc = 0;
    for (int i = 0; i <= M; i++) {
        if (i > 0) {
            acc += W_cost[i];
        }
        
        if (dp[i] != INF) {
            cht.add(-i * W, dp[i] - prefC[i] + acc);
        }
        
        if (i < M) {
            long long min_prev = cht.query(W);
            dp[i + 1] = min(dp[i + 1], min_prev + prefC[i + 1] - acc + (i + 1) * W);
        }
    }

    long long ans = dp[M];
    
    long long driver_water_cost = (X / T + 1) * W;
    long long all_passenger_water_cost = 0;
    
    for (int i = 0; i < N; i++) {
        long long div = S[i] / T;
        all_passenger_water_cost += div * W;
    }
    
    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...