Submission #1270752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270752		rafamiune	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	285 ms	522020 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 = 998244353;
const int MAXN = 2e2 + 5; // MUDAR O LIMITE
const int INF1 = 1e9 + 5;
const long long INF = 1e18 + 5;

int dp[2*MAXN][2*MAXN][MAXN][2];

void solve() {

    int n, L;
    cin >> n >> L;
    vector<int> x(2*MAXN), t(2*MAXN);
    for(int i = 1; i <= n; i ++) {
        cin >> x[i];
        x[i+n+1] = x[i];
    }
    for(int i = 1; i <= n; i ++) {
        cin >> t[i];
        t[i+n+1] = t[i];
    }
    x[0] = 0; t[0] = -1; x[n+1] = 0; t[n+1] = -1;

    vector<vector<int>> dist(2*MAXN, vector<int>(2*MAXN));
    for(int i = 0; i <= 2*n+1; i++) {
        for(int j = 0; j <= 2*n+1; j++) {
            dist[i][j] = min((int)abs(x[i] - x[j]), (int)(L - abs(x[i] - x[j])));
        }
    }
    
    for(int i = 0; i <= 2*n+1; i++) {
        for(int j = 0; j <= 2*n+1; j++) {
            for(int q = 0; q <= n; q++) {
                dp[i][j][q][0] = INF;
                dp[i][j][q][1] = INF;
            }
        }
    }

    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[n+1][n+1][0][0] = 0;
    dp[n+1][n+1][0][1] = 0;
    for(int sz = 1; sz <= n+1; sz++) {
        for(int l = 0; l <= 2*n+1 - sz + 1; l++) {
            for(int q = 0; q <= n; q++) {
                int r = l + sz - 1;
                if(l < 2*n + 1) dp[l][r][q][0] = min(dp[l][r][q][0], dp[l+1][r][q][0] + dist[l+1][l]);
                if(l < 2*n + 1) dp[l][r][q][0] = min(dp[l][r][q][0], dp[l+1][r][q][1] + dist[r][l]);
                if(r > 0) dp[l][r][q][1] = min(dp[l][r][q][1], dp[l][r-1][q][1] + dist[r-1][r]);
                if(r > 0) dp[l][r][q][1] = min(dp[l][r][q][1], dp[l][r-1][q][0] + dist[l][r]);
                if(q >= 1) {
                    if(l < 2*n + 1 && dp[l+1][r][q-1][0] + dist[l+1][l] <= t[l]) {
                        if(l < 2*n + 1) dp[l][r][q][0] = min(dp[l][r][q][0], dp[l+1][r][q-1][0] + dist[l+1][l]);
                    }
                    if(l < 2*n + 1 &&dp[l+1][r][q-1][1] + dist[r][l] <= t[l]) {
                        if(l < 2*n + 1) dp[l][r][q][0] = min(dp[l][r][q][0], dp[l+1][r][q-1][1] + dist[r][l]);
                    }
                    if(r > 0 && dp[l][r-1][q-1][1] + dist[r-1][r] <= t[r]) {
                        dp[l][r][q][1] = min(dp[l][r][q][1], dp[l][r-1][q-1][1] + dist[r-1][r]);
                    }
                    if(r > 0 && dp[l][r-1][q-1][0] + dist[l][r] <= t[r]) {
                        dp[l][r][q][1] = min(dp[l][r][q][1], dp[l][r-1][q-1][0] + dist[l][r]);
                    }
                }
            }
        }
    }

    for(int sz = 1; sz <= n+1; sz++) {
        for(int l = 0; l <= 2*n+1 - sz + 1; l++) {
            for(int q = 0; q <= n; q++) {
                int r = l + sz - 1;
                //cout << l << " " << r << " " << q << " " << 0 << ": " << dp[l][r][q][0] << "\n";
                //cout << l << " " << r << " " << q << " " << 1 << ": " << dp[l][r][q][1] << "\n";
            }
        }
    }

    int ans = 0;
    for(int i = 0; i <= n; i++) {
        for(int q = 0; q <= n; q++) {
            if(dp[i][i+n][q][0] < INF || dp[i][i+n][q][1] < INF) {
                ans = max(ans, q);
            }
        }
    }

    cout << ans << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tt;
    tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
    }

    return 0;
}

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