Submission #879494

#TimeUsernameProblemLanguageResultExecution timeMemory
879494frostray8653Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
95 ms135564 KiB
#include <bits/stdc++.h>
#define int long long
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= I; i++)
using namespace std;
using pii = pair<int, int>;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) { cout << a << " "; dbg(b...); }
void ent() { cout << "\n"; }
const int INF = 1e17;

const int N = 205;
int a[N], t[N];
int dp[2][N][N][N];

signed main() {
    IO;

    int n, len;
    cin >> n >> len;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> t[i];

    int ans = 0;
    fill(&dp[0][0][0][0], &dp[0][0][0][0] + 2 * N * N * N, INF);
    
    dp[0][0][0][n] = 0;
    for (int i = 0; i < n; i++) {
        for (int r = n; r >= 1; r--) {
            // Left : 0
            for (int l = 0; l <= r; l++) {
                if (dp[0][i][l][r] < INF) {
                    int ti, nxt_i;
                    ti = dp[0][i][l][r] + (a[l + 1] - a[l]);
                    nxt_i = i + (ti <= t[l + 1]);
                    dp[0][nxt_i][l + 1][r] = min(dp[0][nxt_i][l + 1][r], ti);

                    ti = dp[0][i][l][r] + (a[l] - 0 + len - a[r]);
                    nxt_i = i + (ti <= t[r]);
                    dp[1][nxt_i][l + 1][r] = min(dp[1][nxt_i][l + 1][r], ti);
                }
            }
            // Right : 1
            for (int l = 0; l <= r; l++) {
                if (dp[1][i][l][r] < INF) {
                    int ti, nxt_i;
                    ti = dp[1][i][l][r] + (len - a[r] + a[l] - 0);
                    nxt_i = i + (ti <= t[l]);
                    dp[0][nxt_i][l][r - 1] = min(dp[0][nxt_i][l][r - 1], ti);

                    ti = dp[1][i][l][r] + (a[r] - a[r - 1]);
                    nxt_i = i + (ti <= t[r - 1]);
                    dp[1][nxt_i][l][r - 1] = min(dp[1][nxt_i][l][r - 1], ti);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int l = 1; l <= n; l++)
            for (int r = l; r <= n; r++)
                if (dp[0][i][l][r] < INF || dp[1][i][l][r] < INF)
                    ans = max(ans, i);
    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...