Submission #1280872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280872		vitaliiv	Long Distance Coach (JOI17_coach)	C++20	0 / 100	1 ms	580 KiB

coach

#include <bits/stdc++.h>

using namespace std;

struct DP {
    __int128 val;
    vector<int64_t> p;
    DP() : val(2e28), p(0) {}
};

int64_t calc(int64_t r, int64_t d, int64_t t) {
    if (d <= r) {
        return (r - d) / t + 1;
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
    int64_t xx, xn, xm, xw, xt;
    cin >> xx >> xn >> xm >> xw >> xt;
    __int128 x = xx, n = xn, m = xm, w = xw, t = xt;
    vector<vector<DP>> dp(n + 2, vector<DP>(m + 1));
    vector<int64_t> s(n);
    for (int64_t i = 0; i < n; ++i) {
        int64_t xx;
        cin >> xx;
        s[i] = xx;
    }
    vector<pair<int64_t, int64_t>> a(m);
    for (int64_t i = 0; i < m; ++i) {
        int64_t xx, xy;
        cin >> xx >> xy;
        a[i].first = xx;
        a[i].second = xy;
    }
    s.insert(s.begin(), 0);
    s.push_back(x);
    n += 2;
    dp[0][m].val = 0;
    for (int64_t i = 0; i < m; ++i) {
        dp[0][m].p.push_back(i);
    }
    for (int64_t i = 0; i < n - 1; ++i) {
        for (int64_t j = 0; j <= m; ++j) {
            if (dp[i][j].p.size() != j) continue;
            int64_t mld = (s[i + 1] / t) * t;
            vector<pair<int64_t, int64_t>> pld;
            for (auto k : dp[i][j].p) {
                int64_t tmp = a[k].first + mld;
                if (tmp <= s[i + 1]) {
                    pld.emplace_back(k, tmp);
                }
            }
            sort(pld.begin(), pld.end(), [&](auto l, auto r) { return l.second > r.second; });
            DP x = dp[i][j];
            if (x.val < dp[i + 1][j].val) {
                dp[i + 1][j] = x;
            }
            for (int64_t k = 0; k < pld.size(); ++k) {
                x.val += calc(mld, a[pld[k].first].first, t) * w;
                x.val += a[pld[k].first].second;
                x.p.erase(find(x.p.begin(), x.p.end(), pld[k].first));
                if (x.val < dp[i + 1][j - k - 1].val) {
                    dp[i + 1][j - k - 1] = x;
                }
            }
        }
    }
    __int128 ans = 2e28;
    for (int64_t i = 0; i <= m; ++i) {
        if (dp[n - 1][i].p.size() == i) {
            int64_t cur = 0;
            for (int64_t j = 0; j < i; ++j) {
                cur += calc(x, a[dp[n - 1][i].p[j]].first, t) * w;
            }
            ans = min(ans, dp[n - 1][i].val + cur);
        }
    }
    ans += calc(x, 0, t) * w;
    string ss;
    while (ans != 0) {
        ss = string(1, int(ans % 10) + '0') + ss;
        ans /= 10;
    }
    cout << ss << '\n';
    return 0;
}

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