제출 #879486

#제출 시각아이디문제언어결과실행 시간메모리
879486frostray8653Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
120 ms135656 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() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    IO;

    int n, tot;
    cin >> n >> tot;
    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 = 1; l <= r; l++) {
                int ti;
                if (i) {
                    ti = dp[0][i - 1][l - 1][r] + (a[l] - a[l - 1]);
                    if (ti <= t[l])
                        dp[0][i][l][r] = min(dp[0][i][l][r], ti);
                    if (r + 1 <= n) {
                        ti = dp[1][i - 1][l][r + 1] + (tot - a[r + 1] + a[l] - 0);
                        if (ti <= t[l])
                            dp[0][i][l][r] = min(dp[0][i][l][r], ti);
                    }
                }
                ti = dp[0][i][l - 1][r] + (a[l] - a[l - 1]);
                dp[0][i][l][r] = min(dp[0][i][l][r], ti);
                if (r + 1 <= n) {
                    ti = dp[1][i][l][r + 1] + (tot - a[r + 1] + a[l] - 0);
                    dp[0][i][l][r] = min(dp[0][i][l][r], ti);
                }
                if (dp[0][i][l][r] < INF) {
                    // dbg(0, i, l, r, ':', dp[0][i][l][r]), ent();
                    ans = max(ans, i);
                }
            }
            // Right : 1
            for (int l = 1; l <= r; l++) {
                int ti;
                if (i) {
                    ti = dp[0][i - 1][l - 1][r] + (a[l - 1] - 0 + tot - a[r]);
                    if (ti <= t[r])
                        dp[1][i][l][r] = min(dp[1][i][l][r], ti);
                    ti = dp[1][i - 1][l][r + 1] + (a[r + 1] - a[r]);
                    if (ti <= t[r])
                        dp[1][i][l][r] = min(dp[1][i][l][r], ti);
                }
                ti = dp[0][i][l - 1][r] + (a[l - 1] - 0 + tot - a[r]);
                dp[1][i][l][r] = min(dp[1][i][l][r], ti);
                if (r + 1 <= n) {
                    ti = dp[1][i][l][r + 1] + (a[r + 1] - a[r]);
                    dp[1][i][l][r] = min(dp[1][i][l][r], ti);
                }
                if (dp[1][i][l][r] < INF) {
                    // dbg(1, i, l, r, ':', dp[1][i][l][r]), ent();
                    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...