Submission #222554

#	Time	Username	Problem	Language	Result	Execution time	Memory
222554		astoria	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	408 ms	527008 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,l;
int a[405],t[405];
int dp[405][405][205][2];
#define INF (int) 1e17

void chkmin(int &x,int y){x=x<y?x:y;}
int dis(int x,int y){return abs(a[x]-a[y]);}
bool ok(int u,int VAL){return t[u]>=VAL;}

int32_t main(){
	for(int i=0; i<405; i++){
		for(int j=0; j<405; j++){
			for(int k=0; k<205; k++){
				dp[i][j][k][0] = 1e17;
				dp[i][j][k][1] = 1e17;
			}
		}
	}
	
	cin>>n>>l;
	for(int i=1; i<=n; i++){
		cin>>a[i+n];
		a[i] = -(l-a[i+n]);
	}
	for(int i=1; i<=n; i++){
		cin>>t[i]; t[i+n]=t[i];
	}
	for(int i=1; i<=2*n; i++){
		dp[i][i][0][0] = abs(a[i]);
		if(t[i]>=abs(a[i])) dp[i][i][1][0] = abs(a[i]);
	}
	
	for(int l=1; l<n; l++){
		for(int x=1; x+l-1<=2*n; x++){
			int y = x+l-1;
			for(int k=0; k<=l; k++){
				if(dp[x][y][k][0]!=1e17){
					int now=x,u=0;
					if(x-1&&dis(now,x-1)<=INF)chkmin(dp[x-1][y][k+ok(x-1,dp[x][y][k][u]+dis(now,x-1))][0],dp[x][y][k][u]+dis(now,x-1));
					if(y+1<=2*n&&dis(now,y+1)<=INF)chkmin(dp[x][y+1][k+ok(y+1,dp[x][y][k][u]+dis(now,y+1))][1],dp[x][y][k][u]+dis(now,y+1));
				}
				if(dp[x][y][k][1]!=1e17){
					int now=y,u=1;
					if(x-1&&dis(now,x-1)<=INF)chkmin(dp[x-1][y][k+ok(x-1,dp[x][y][k][u]+dis(now,x-1))][0],dp[x][y][k][u]+dis(now,x-1));
					if(y+1<=2*n&&dis(now,y+1)<=INF)chkmin(dp[x][y+1][k+ok(y+1,dp[x][y][k][u]+dis(now,y+1))][1],dp[x][y][k][u]+dis(now,y+1));
				}
			}
		}
	}
	
	for(int k=n;k>=0;k--){
		for(int x=1;x+k-1<=2*n;x++){
			for(int y=x+k-1;y<=2*n;y++){
				if(dp[x][y][k][0]!=INF||dp[x][y][k][1]!=INF){
					cout<<k; return 0;
				}
			}
		}
	}
}

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