Submission #520964

#	Time	Username	Problem	Language	Result	Execution time	Memory
520964		AdamGS	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	51 ms	66556 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=207, INF=1e9+7;
int X[LIM], T[LIM], dp[LIM][LIM][LIM][2];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, ans=0;
	cin >> n >> m;
	rep(i, n) cin >> X[i+1];
	rep(i, n) cin >> T[i+1];
	rep(i, n+1) rep(j, n+1) rep(c, n+1) rep(l, 2) dp[i][j][c][l]=INF;
	dp[0][0][0][0]=0;
	rep(i, n+1) rep(j, n-i+1) rep(c, i+j+1) rep(l, 2) if(dp[i][j][c][l]<INF) {
		ans=max(ans, c);
		if(i+j==n) continue;
		int x=dp[i][j][c][l];
		if(!l) {
			dp[i+1][j][c][0]=min(dp[i+1][j][c][0], x+X[i+1]-X[i]);
			if(x+X[i+1]-X[i]<=T[i+1]) {
				dp[i+1][j][c+1][0]=min(dp[i+1][j][c+1][0], x+X[i+1]-X[i]);
			}
			dp[i][j+1][c][1]=min(dp[i][j+1][c][1], x+X[i]+m-X[n-j]);
			if(x+X[i]+m-X[n-j]<=T[n-j]) {
				dp[i][j+1][c+1][1]=min(dp[i][j+1][c+1][1], x+X[i]+m-X[n-j]);
			}
		} else {
			dp[i+1][j][c][0]=min(dp[i+1][j][c][0], x+m-X[n-j+1]+X[i+1]);
			if(x+m-X[n-j+1]+X[i+1]<=T[i+1]) {
				dp[i+1][j][c+1][0]=min(dp[i+1][j][c+1][0], x+m-X[n-j+1]+X[i+1]);
			}
			dp[i][j+1][c][1]=min(dp[i][j+1][c][1], x+X[n-j+1]-X[n-j]);
			if(x+X[n-j+1]-X[n-j]<=T[n-j]) {
				dp[i][j+1][c+1][1]=min(dp[i][j+1][c+1][1], x+X[n-j+1]-X[n-j]);
			}
		}
	}
	cout << ans << '\n';
}

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