Submission #959815

#	Time	Username	Problem	Language	Result	Execution time	Memory
959815		happy_node	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	71 ms	135368 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=205;

ll N,L;
ll X[MX], T[MX], dp[MX][MX][MX][2];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int j=0;j<MX;j++)
			for(int x=0;x<MX;x++)
				for(int k=0;k<2;k++)
					dp[i][j][x][k]=1e18;

	cin>>N>>L;
	for(int i=1;i<=N;i++) cin>>X[i];
	for(int i=1;i<=N;i++) cin>>T[i];

	dp[0][N+1][0][0]=0;
	dp[0][N+1][0][1]=0;
	X[N+1]=L;

	for(int l=0;l<=N;l++) {
		for(int r=N+1;r>l;r--) {
			for(int x=0;x<=N;x++) {
				// gerakin kanan
				ll nxt=dp[l][r][x][0]+X[l+1]-X[l];
				if(nxt<=T[l+1])
					dp[l+1][r][x+1][0]=min(dp[l+1][r][x+1][0],nxt);
				else
					dp[l+1][r][x][0]=min(dp[l+1][r][x][0],nxt);

				nxt=dp[l][r][x][1]+L-X[r]+X[l+1];
				if(nxt<=T[l+1])
					dp[l+1][r][x+1][0]=min(dp[l+1][r][x+1][0],nxt);
				else
					dp[l+1][r][x][0]=min(dp[l+1][r][x][0],nxt);

				// gerakin kiri
				nxt=dp[l][r][x][1]+X[r]-X[r-1];
				if(nxt<=T[r-1]) 
					dp[l][r-1][x+1][1]=min(dp[l][r-1][x+1][1],nxt);
				else
					dp[l][r-1][x][1]=min(dp[l][r-1][x][1],nxt);

				nxt=dp[l][r][x][0]+X[l]+L-X[r-1];
				if(nxt<=T[r-1])
					dp[l][r-1][x+1][1]=min(dp[l][r-1][x+1][1],nxt);
				else
					dp[l][r-1][x][1]=min(dp[l][r-1][x][1],nxt);
			}
		}
	}
	
	int ans=0;

	for(int l=0;l<=N;l++) {
		for(int r=N+1;r>l;r--) {
			for(int x=0;x<=N;x++) {
				if(min(dp[l][r][x][0],dp[l][r][x][1])!=1e18)
					ans=max(ans,x);
			}
		}
	}

	cout<<ans<<'\n';
}

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