Submission #1000382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000382		makrav	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	83 ms	145428 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first 
#define sc second 
#define pb push_back
#define int ll

int dp[210][210][210][2];

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, l; cin >> n >> l;
    vector<int> x(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> x[i];
    vector<int> t(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> t[i];
    auto getd = [&](int i, int j) {
        return min(abs(x[i] - x[j]), l - abs(x[i] - x[j]));
    };
    for (int i = 0; i <= 209; i++) {
        for (int j = 0; j <= 209;j++) {
            for (int cnt = 0; cnt <= 209; cnt++) {
                for (int I = 0; I < 2; I++) dp[i][j][cnt][I] = 1e15;
            }
        }
    }
    dp[1][0][1][0] = 0;
    dp[1][0][1][1] = 0;
    for (int cnt = 2; cnt <= n + 1; cnt++) {
        for (int left = 1; left <= cnt; left++) {
            int right = cnt - left;
            for (int C = 1; C <= cnt; C++) {
                auto relax = [&](int side, int val) {
                    if (val < 1e15) {
                        dp[left][right][C][side] = min(dp[left][right][C][side], val);
                    }
                };
                {
                    int prev_left = (left == 1 ? n : left - 2);
                    int prev_right = (right == 0 ? 0 : n - right + 1);
                    if (dp[left - 1][right][C - 1][0] + getd(prev_left, left - 1) <= t[left - 1]) {
                        relax(0, dp[left - 1][right][C - 1][0] + getd(prev_left, left - 1));
                    }
                    if (dp[left - 1][right][C][0] + getd(prev_left, left - 1) > t[left - 1]) {
                        relax(0, dp[left - 1][right][C][0] + getd(prev_left, left - 1));
                    }
                    if (dp[left - 1][right][C - 1][1] + getd(prev_right, left - 1) <= t[left - 1]) {
                        relax(0, dp[left - 1][right][C - 1][1] + getd(prev_right, left - 1));
                    }
                    if (dp[left - 1][right][C][1] + getd(prev_right, left - 1) > t[left - 1]) {
                        relax(0, dp[left - 1][right][C][1] + getd(prev_right, left - 1));
                    }
                }
                if (right) {
                    int prev_left = left - 1, prev_right = (right == 1 ? 0 : n - (right - 1) + 1);
                    int cur = n - right + 1;
                    if (dp[left][right - 1][C - 1][0] + getd(prev_left, cur) <= t[cur]) {
                        relax(1, dp[left][right - 1][C - 1][0] + getd(prev_left, cur));
                    }
                    if (dp[left][right - 1][C][0] + getd(prev_left, cur) > t[cur]) {
                        relax(1, dp[left][right - 1][C][0] + getd(prev_left, cur));
                    }
                    if (dp[left][right - 1][C - 1][1] + getd(prev_right, cur) <= t[cur]) {
                        relax(1, dp[left][right - 1][C - 1][1] + getd(prev_right, cur));
                    }
                    if (dp[left][right - 1][C][1] + getd(prev_right, cur) > t[cur]) {
                        relax(1, dp[left][right - 1][C][1] + getd(prev_right, cur));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int left = 1; left <= n + 1; left++) {
        for (int cnt = 1; cnt <= n + 1; cnt++) {
            if (dp[left][n + 1 - left][cnt][0] < 1e15 || dp[left][n + 1 - left][cnt][1] < 1e15) ans = max(ans, cnt); 
        }
    }
    cout << ans - 1 << '\n';

    return 0;
}

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