Submission #583904

#	Time	Username	Problem	Language	Result	Execution time	Memory
583904		pakhomovee	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	873 ms	82432 KiB

ho_t3

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <queue>

using namespace std;

const int inf = 1e9 + 1;
const int maxn = 201;
int dp[maxn][maxn][maxn][2];
bool used[maxn][maxn][maxn][2];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, l;
    cin >> n >> l;
    vector<int> x(n);
    for (int& i : x) {
        cin >> i;
    }
    vector<int> t(n);
    for (int& i : t) {
        cin >> i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k <= n; ++k) {
                dp[i][j][k][0] = dp[i][j][k][1] = inf;
            }
        }
    }
    auto dist = [&](int i, int j) {
        return min(abs(x[i] - x[j]), l - max(x[i], x[j]) + min(x[i], x[j]));
    };
    auto d = [&] (int i) {
        return min(x[i], l - x[i]);
    };
    priority_queue<pair<int, pair<pair<int, int>, pair<int, int>>>> q;
    if (d(0) <= t[0]) {
        dp[0][0][1][1] = d(0);
        q.push({ -dp[0][0][1][1], { { 0, 0 }, { 1 , 1 } } });
    } else {
        dp[0][0][0][1] = d(0);
        q.push({ -dp[0][0][0][1], { { 0, 0 }, { 0, 1 } } });
    }
    if (d(n - 1) <= t[n - 1]) {
        dp[n - 1][n - 1][1][0] = d(n - 1);
        q.push({ -dp[n - 1][n - 1][1][0], { { n - 1, n - 1 }, { 1, 0 } } });
    } else {
        dp[n - 1][n - 1][0][0] = d(n - 1);
        q.push({ -dp[n - 1][n - 1][0][0], { { n - 1, n - 1 }, { 0, 0 } } });
    }
    while (!q.empty()) {
        auto [a, b] = q.top().second;
        auto [l, r] = a;
        auto [c, s] = b;
        q.pop();
        if (used[l][r][c][s]) continue;
        used[l][r][c][s] = 1;
        if ((r + 1) % n == l) continue;
        if (s) {
            int rp = (r + 1) % n;
            int tp = dp[l][r][c][s] + dist(r, rp);
            int nc = c;
            if (tp <= t[rp]) {
                ++nc;
            }
            if (tp < dp[l][rp][nc][s]) {
                dp[l][rp][nc][s] = tp;
                q.push({ -dp[l][rp][nc][s], { { l, rp }, { nc, s } } });
            }
        } else {
            int lp = (l - 1 + n) % n;
            int tp = dp[l][r][c][s] + dist(l, lp);
            int nc = c;
            if (tp <= t[lp]) {
                ++nc;
            }
            if (tp < dp[lp][r][nc][s]) {
                dp[lp][r][nc][s] = tp;
                q.push({ -dp[lp][r][nc][s], { { lp, r }, { nc, s } } });
            }
        }
        if (dp[l][r][c][s ^ 1] > dp[l][r][c][s] + dist(l, r)) {
            dp[l][r][c][s ^ 1] = dp[l][r][c][s] + dist(l, r);
            q.push({ -dp[l][r][c][s ^ 1], { { l, r }, { c, s ^ 1 } } });
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k <= n; ++k) {
                for (int q = 0; q < 2; ++q) {
                    if (dp[i][j][k][q] < inf) {
                        ans = max(ans, k);
                    }
                }
            }
        }
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75