제출 #1269592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269592		rafamiune	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	328 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9 + 7;
const int MAXN = 2e2 + 5;
const long long INF = 1e18 + 5;

int n, d;
vector<int> t(MAXN), x(MAXN);

int dist(int a, int b) {
    if(b >= a) return min(x[b] - x[a], d - (x[b] - x[a]));
    return min(x[a] - x[b], d - (x[a] - x[b]));
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> d;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 1; i <= n; i++) cin >> t[i];
    t[0] = -1;
    x[0] = 0;
    int dp[n+1][n+1][n+1][2]; // dp[l][r][q][flag] =: limpou o intervalo [l,r], está com q e está na direita(1) ou na esquerda(0);
    for(int l = 0; l <= n; l++) for(int r = 0; r <= n; r++) {
        for(int qtd = 0; qtd <= n; qtd ++) {
            dp[l][r][qtd][0] = INF;
            dp[l][r][qtd][1] = INF;
        }
    }
    // 6 25
    // 3 4 7 17 21 23
    // 11 7 17 10 8 10
    for(int l = 0; l <= n; l++) for(int r = l; r <= n; r++) {
        dp[l][r][0][0] = dist(0,r) + dist(r,l);
        dp[l][r][0][1] = dist(0,l) + dist(l,r);
    }
    for(int qtd = 1; qtd <= n; qtd++) {
        for(int sz = 1; sz <= n; sz++) {
            for(int l = 0; l <= n; l++) {
                int r = (l + sz - 1) % (n+1);
                int nl, nr;
                nl = (l < n ? l + 1 : 0);
                nr = (r > 0 ? r - 1 : n);
                dp[l][r][qtd][0] = dp[nl][r][qtd][0] + dist(nl, l);
                if(dp[nl][r][qtd-1][0] + dist(nl, l) <= t[l]) {
                    dp[l][r][qtd][0] = min(dp[l][r][qtd][0], dp[nl][r][qtd-1][0] + dist(nl, l));
                }
                if(dp[nl][r][qtd-1][1] + dist(r, l) <= t[l]) {
                    dp[l][r][qtd][0] = min(dp[l][r][qtd][0], dp[nl][r][qtd-1][1] + dist(r, l));
                }
                dp[l][r][qtd][1] = dp[l][nr][qtd][1] + dist(nr, r);
                if(dp[l][nr][qtd-1][1] + dist(nr, r) <= t[r]) {
                    dp[l][r][qtd][1] = min(dp[l][r][qtd][1], dp[l][nr][qtd-1][1] + dist(nr, r));
                }
                if(dp[l][nr][qtd-1][0] + dist(l, r) <= t[r]) {
                    dp[l][r][qtd][1] = min(dp[l][r][qtd][1], dp[l][nr][qtd-1][0] + dist(l, r));
                }
                //cout << l << " " << r << " " << qtd << " " << 0 << ": " << dp[l][r][qtd][0] << "\n";
                //cout << l << " " << r << " " << qtd << " " << 1 << ": " << dp[l][r][qtd][1] << "\n";
            }
        }
    }

    //cout << dist(5,1) << " " << dp[5][0][2][0] << " " << t[1] << "\n";

    int ans = 0;
    for(int l = 0; l <= n; l++) for(int r = 0; r <= n; r++) {
        for(int qtd = 0; qtd <= n; qtd ++) {
            if(dp[l][r][qtd][0] < INF || dp[l][r][qtd][1] < INF) ans = max(ans, qtd);
        }
    }
    cout << ans << "\n";

    return 0;
}

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