Submission #1253729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253729		gry3125	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	56 ms	135240 KiB

ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

ll n, l; int mx = 0;
ll dp[205][205][2][205] = { };

int main() {
	cin >> n >> l; vector<ll> x(n+5), t(n+5);
    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 < 205; i++) {
    	for (int j = 0; j < 205; j++) {
    		for (int k = 0; k < 205; k++) {
    			dp[i][j][0][k] = 1e18;
    			dp[i][j][1][k] = 1e18;
    		}
    	}
    }
    x[n+1] = l;
    dp[n+1][0][0][0] = 0;
    dp[n+1][0][1][0] = 0;
    if (1) {
	    // dp[n+1][?][1][?]
	    int cur = 0;
	    for (int i = 1; i <= n; i++) {
	    	if (x[i] <= t[i]) cur++;
	    	dp[n+1][i][1][cur] = min(dp[n+1][i][1][cur], x[i]);
	    }
	    // dp[?][0][0][?]
	    cur = 0;
	    for (int i = n; i > 0; i--) {
	    	if (l-x[i] <= t[i]) cur++;
	    	dp[i][0][0][cur] = min(dp[i][0][0][cur], l-x[i]);
	    }
    }
    for (int i = n; i > 0; i--) {
    	for (int j = 1; j < i; j++) {
    		for (int k = 1; k <= n; k++) {
    			// dp[i][j][0][?]: i+1 -> i
    			ll cur = dp[i+1][j][0][k] + x[i+1] - x[i];
    			dp[i][j][0][k] = min(dp[i][j][0][k], cur);
    			cur = dp[i+1][j][0][k-1] + x[i+1] - x[i];
    			if (cur <= t[i]) {
    				dp[i][j][0][k] = min(dp[i][j][0][k], cur);
    			}
    			// dp[i][j][0][?]: j -> i
    			cur = dp[i+1][j][1][k] + l - x[i] + x[j];
    			dp[i][j][0][k] = min(dp[i][j][0][k], cur);
    			cur = dp[i+1][j][1][k-1] + x[i] - x[j];
    			if (cur <= t[i]) {
    				dp[i][j][0][k] = min(dp[i][j][0][k], cur);
    			}
    			// dp[i][j][1][?]: j-1 -> j
    			cur = dp[i][j-1][1][k] + x[j] - x[j-1];
    			dp[i][j][1][k] = min(dp[i][j][1][k], cur);
    			cur = dp[i][j-1][1][k-1] + x[j] - x[j-1];
    			if (cur <= t[j]) {
    				dp[i][j][1][k] = min(dp[i][j][1][k], cur);
    			}
    			// dp[i][j][1][?]: i -> j
    			cur = dp[i][j-1][0][k] + l - x[i] + x[j];
    			dp[i][j][1][k] = min(dp[i][j][1][k], cur);
    			cur = dp[i][j-1][0][k-1] + l - x[i] + x[j];
    			if (cur <= t[j]) {
    				dp[i][j][1][k] = min(dp[i][j][1][k], cur);
    			}
    		}
    	}
    }
    for (int i = 0; i <= n+1; i++) {
    	for (int j = 0; j <= n+1; j++) {
    		for (int k = 0; k <= n; k++) {
    			if (dp[i][j][0][k] < 1e18) mx = max(mx, k);
    			if (dp[i][j][1][k] < 1e18) mx = max(mx, k);
    		}
    	}
    }
    cout << mx; 
    return 0;
}

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