Submission #1315415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315415		vedchoudhary	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	92 ms	126296 KiB

ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

using ll = long long;
#define int ll

int n,l;
const int INF = (int)4e18;
int dp[200][200][201][2]; // s,e,stamps,l0 r1

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int i = 0; i < 200; i++) for(int j = 0; j < 200; j++) for(int k = 0; k < 201; k++) {
        dp[i][j][k][0] = INF;
        dp[i][j][k][1] = INF;
    }
    
    cin >> n >> l;
    vector<int> x(n); for(int i = 0; i < n; i++) cin >> x[i];
    vector<int> t(n); for(int i = 0; i < n; i++) cin >> t[i];

    for(int i = 0; i < n; i++) {
        dp[i][i][0][0] = min(x[i],l-x[i]);
        dp[i][i][0][1] = min(x[i],l-x[i]);
        if(dp[i][i][0][0]<=t[i]) {
            dp[i][i][1][0] = dp[i][i][0][0];
            dp[i][i][1][1] = dp[i][i][0][0];
        }
    }

    auto dist = [&](const int& a, const int& b) -> ll {
        return min(abs(a-b),l-abs(a-b));
    };

    for(int len = 2; len <= n; len++) {
        for(int s = 0; s < n; s++) {
            int e = (s+len-1)%n;
            for(int k = 0; k < len; k++) {
                //choose l in both cases
                int opt = min(dp[(s+1+n)%n][e][k][0]+dist(x[(s+1+n)%n],x[s]),dp[(s+1+n)%n][e][k][1]+dist(x[e],x[s]));
                int nk = k + (opt<=t[s]);
                dp[s][e][nk][0] = min(dp[s][e][nk][0],opt);
                //choose r in both cases
                opt = min(dp[s][(e-1+n)%n][k][0]+dist(x[s],x[e]),dp[s][(e-1+n)%n][k][1]+dist(x[(e-1+n)%n],x[e]));
                nk = k + (opt<=t[e]);
                dp[s][e][nk][1] = min(dp[s][e][nk][1],opt);
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < 200; i++) for(int j = 0; j < 200; j++) for(int k = 0; k < 201; k++) {
        if(dp[i][j][k][0] < INF) ans = max(ans,k);
        if(dp[i][j][k][1] < INF) ans = max(ans,k);
    }
    
    cout << ans << "\n";

    return 0;
}

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