제출 #1159236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159236		OI_Account	Long Distance Coach (JOI17_coach)	C++20	100 / 100	94 ms	21168 KiB

coach

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

#define M first
#define B second

typedef long long ll;
typedef pair<ll, ll> line;

const int N = 200'000;

ll x, n, m, w, t, s[N + 10];
ll d[N + 10], c[N + 10];
pair<ll, ll> p[N + 10];
ll a[N + 10], dp[N + 10], all[N + 10];
ll sum[N + 10], f[N + 10];

void readInput() {
    cin >> x >> n >> m >> w >> t;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= m; i++)
        cin >> p[i].first >> p[i].second;
}

void initInput() {
    sort(s + 1, s + n + 1);
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= m; i++) {
        d[i] = p[i].first;
        c[i] = p[i].second;
    }
}

void calcA() {
    for (int i = 1; i <= m; i++)
        a[i] = -1;
    for (int i = 0; i <= n; i++) {
        ll nxt = (i == n? x: s[i + 1]);
        int idx = lower_bound(d + 1, d + m + 1, nxt % t) - d;
        if (idx != 1 && a[idx - 1] == -1)
            a[idx - 1] = (nxt - 1) / t;
    }
}

void calcAll() {
    for (int i = 1; i <= m; i++)
        all[i] = x / t + (d[i] < x % t);
    all[0] = x / t + 1;
}

void calcSum() {
    for (int i = 1; i <= m; i++)
        sum[i] = sum[i - 1] + c[i];
}

vector<pair<ll, line>> vec;

ll getVal(line l, ll x) {
    return l.B + x * l.M;
}

ll getIdx(line l1, line l2) {
    return (l2.B - l1.B + (l1.M - l2.M - 1)) / (l1.M - l2.M);
}

void addLine(line l) {
    while (!vec.empty()) {
        ll val1 = getVal(vec.back().second, vec.back().first);
        ll val2 = getVal(l, vec.back().first);
        if (val1 <= val2)
            vec.pop_back();
        else
            break;
    }
    if (vec.empty())
        vec.push_back({0, l});
    else {
        line l2 = vec.back().second;
        vec.push_back({getIdx(l, l2), l});
    }
}

ll getMax(ll x) {
    int idx = upper_bound(vec.begin(), vec.end(), make_pair(x + 1, line(-1, -1))) - vec.begin();
    return getVal(vec[idx - 1].second, x);
}

void calcDP() {
    vec.push_back({0, line(0, 0)});
    for (int i = 1; i <= m; i++) {
        dp[i] = all[i] * w + dp[i - 1];
        if (a[i] != -1) {
            ll case2 = getMax(a[i] * w);
            dp[i] = min(dp[i], sum[i] + a[i] * w * i - case2);
        }
        f[i] = dp[i] - sum[i];
        addLine(line(i, -f[i]));
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    initInput();
    calcA();
    calcAll();
    calcSum();
    calcDP();
    cout << dp[m] + all[0] * w << flush;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29