Submission #1299729

#TimeUsernameProblemLanguageResultExecution timeMemory
1299729azamuraiCollecting Stamps 3 (JOI20_ho_t3)C++20
25 / 100
423 ms34476 KiB
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define Sz(x) (int)x.size()

using namespace std;

const int N = 205;
const int inf = INT_MAX;
int n, l, x[N], t[N], dp[2][N][N][N];

int dist(int a, int b) {
    if (a > b) swap(a, b);
    return min(b - a, l - b + a);
}

void solve() {
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            for (int k = 0; k <= n; k++) {
                dp[0][i][j][k] = dp[1][i][j][k] = inf;
            }
        }
    }
    dp[0][0][0][0] = dp[1][0][0][0] = 0;
    for (int k = 0; k <= n; k++) {
        for (int tp = 0; tp < 2; tp++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n - i; j++) {
                    if (dp[tp][i][j][k] == inf) continue;
                    int time = dp[tp][i][j][k], pos, k2 = k;
                    int time2 = time;
                    if (tp == 0) {
                        if (i == 0) pos = 0;
                        else pos = x[i];
                    }
                    else {
                        if (j == 0) pos = 0;
                        else pos = x[n - j + 1];
                    }
                    int pos2 = pos;
                    for (int i2 = i + 1; i2 + j <= n; i2++) {
                        time += dist(pos, x[i2]);
                        pos = x[i2];
                        if (time <= t[i2]) k2++;
                        dp[0][i2][j][k2] = min(dp[0][i2][j][k2], time);
                    }
                    pos = pos2, k2 = k, time = time2;
                    for (int j2 = j + 1; j2 + i <= n; j2++) {
                        time += dist(pos, x[n - j2 + 1]);
                        pos = x[n - j2 + 1];
                        if (time <= t[n - j2 + 1]) k2++;
                        dp[1][i][j2][k2] = min(dp[1][i][j2][k2], time);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int tp = 0; tp < 2; tp++) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                for (int k = 0; k <= n; k++) {
                    if (dp[tp][i][j][k] != inf) ans = max(ans, k);
                }
            }
        }
    }   
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;

    while (tt--) {
        solve();
        // cout << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...