Submission #236837

#	Time	Username	Problem	Language	Result	Execution time	Memory
236837		wwdd	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	439 ms	135544 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 210;
const ll INFL = 1e18;
ll dp[2][MN][MN][MN];
ll w[MN],x[MN];
int main() {
	ll n,len;
	cin >> n >> len;
	w[0] = 0;
	for(int i=0;i<n;i++) {
		cin >> w[i+1];
	}
	x[0] = -1;
	for(int i=0;i<n;i++) {
		cin >> x[i+1];
	}
	for(int i=0;i<2;i++) {
		for(int j=0;j<=n;j++) {
			for(int k=0;k<=n+1;k++) {
				for(int l=0;l<=n;l++) {
					dp[i][j][k][l] = INFL;
				}
			}
		}
	}
	dp[0][0][0][0] = dp[1][0][0][0]= 0;
	for(int l=0;l<=n;l++) {
		for(int k=0;k<n;k++) {
			for(int j=0;j<=n;j++) {
				for(int i=0;i<2;i++) {
					if(dp[i][j][k][l] >= INFL) {continue;}
					ll dr,dl;
					int nr = (j+k+1)%(n+1);
					int nl = (j+n)%(n+1);
					if(i) {
						int ro = (j+k)%(n+1);
						dr = ((w[nr]-w[ro])+len)%len;
						dl = ((w[ro]-w[nl])+len)%len;
					} else {
						dr = ((w[nr]-w[j])+len)%len;
						dl = ((w[j]-w[nl])+len)%len;
					}
					int cor = l, col=l;
					if(dp[i][j][k][l]+dr <= x[nr]) {
						cor++;
					}
					if(dp[i][j][k][l]+dl <= x[nl]) {
						col++;
					}
					dp[1][j][k+1][cor] = min(dp[1][j][k+1][cor],dp[i][j][k][l]+dr);
					dp[0][nl][k+1][col] = min(dp[0][nl][k+1][col],dp[i][j][k][l]+dl);
				}
			}
		}
	}
	int res = 0;
	for(int i=0;i<2;i++) {
		for(int j=0;j<=n;j++) {
			for(int k=0;k<=n+1;k++) {
				for(int l=0;l<=n;l++) {
					if(dp[i][j][k][l] < INFL) {
						res = max(res,l);
					}
				}
			}
		}
	}
	cout << res << '\n';
}

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