Submission #879494

#	Time	Username	Problem	Language	Result	Execution time	Memory
879494		frostray8653	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	95 ms	135564 KiB

ho_t3

#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;
}

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