Submission #1269606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269606		rafamiune	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	0 ms	324 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;
int dp[205][205][205][2]; 
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;

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

    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