제출 #704002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704002		KenIsGenius	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	197 ms	130880 KiB

ho_t3

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define int long long
using namespace std;

#ifdef LOCAL
#define WOSAOJI freopen("in.txt", "r", stdin);
#else 
#define WOSAOJI ios_base::sync_with_stdio(0), cin.tie(0);
#endif

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

int n, L, ans;
int x[205], t[205];
int dp[205][205][205][2];

void upd(int l, int r, int y, int dir) {
    int now = dp[l][r][y][dir];
    if (now == 1ll << 60) return;
    chmax(ans, y);
    int nxt = (l + n) % (n + 1);
    int now1;
    if (dir == 0) now1 = now + (x[l] - x[nxt] + L) % L;
    else now1 = now + (x[r] - x[nxt] + L) % L;
    if (nxt != r)
        chmin(dp[nxt][r][y + (now1 <= t[nxt])][0], now1);
    nxt = (r + 1) % (n + 1);
    if (dir == 0) now1 = now + (x[nxt] - x[l] + L) % L;
    else now1 = now + (x[nxt] - x[r] + L) % L;
    if (nxt != l)
        chmin(dp[l][nxt][y + (now1 <= t[nxt])][1], now1);
}

signed main() {
    WOSAOJI
    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; j++) {
            for (int l = 0; l <= n; l++) {
                for (int k = 0; k < 2; k++)
                    dp[i][j][l][k] = 1ll << 60;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    upd(0, 0, 0, 0); upd(0, 0, 0, 1);
    for (int len = 1; len <= n; len++) {
        for (int l = n + 1; l >= 0; l--) {
            int r = (l + len) % (n + 1);
            if (l + len <= n) break;
            for (int y = 0; y <= n; y++) {
                upd(l % (n + 1), r, y, 0);
                upd(l % (n + 1), r, y, 1);
            }
        }
    }
    cout << ans << '\n';
}

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