Submission #524599

#	Time	Username	Problem	Language	Result	Execution time	Memory
524599		mosiashvililuka	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	90 ms	135940 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const long long N=1000000009LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,L,dp[209][209][209][2],k,pas;
pair <long long, long long> p[209];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>L;
	for(i=1; i<=a; i++){
		cin>>p[i].first;
	}
	for(i=1; i<=a; i++){
		cin>>p[i].second;
	}
	for(i=0; i<=a+2; i++){
		for(j=0; j<=a+2; j++){
			for(ii=0; ii<=a+2; ii++){
				dp[i][j][ii][0]=dp[i][j][ii][1]=N;
			}
		}
	}
	dp[a+1][0][0][0]=dp[a+1][0][0][1]=0;
	p[a+1].first=L;
	for(ii=1; ii<=a; ii++){
		for(j=0; j<=ii; j++){
			i=ii-j;i=a+1-i;
			for(k=0; k<=ii; k++){
				if(j!=0){
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][1]+p[j].first-p[j-1].first);
					if(k>0&&dp[i][j-1][k-1][1]+p[j].first-p[j-1].first<=p[j].second){
						dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k-1][1]+p[j].first-p[j-1].first);
					}
					zx=p[j].first+L-p[i].first;
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][0]+zx);
					if(k>0&&dp[i][j-1][k-1][0]+zx<=p[j].second){
						dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k-1][0]+zx);
					}
				}
				if(i!=a+1){
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k][0]+p[i+1].first-p[i].first);
					if(k>0&&dp[i+1][j][k-1][0]+p[i+1].first-p[i].first<=p[i].second){
						dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k-1][0]+p[i+1].first-p[i].first);
					}
					zx=L-p[i].first+p[j].first;
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k][1]+zx);
					if(k>0&&dp[i+1][j][k-1][1]+zx<=p[i].second){
						dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k-1][1]+zx);
					}
				}
			}
		}
	}
	for(i=0; i<=a+1; i++){
		for(j=0; j<=a+1; j++){
			for(ii=0; ii<=a+1; ii++){
				if(dp[i][j][ii][0]!=N){
					pas=max(pas,ii);
				}
				if(dp[i][j][ii][1]!=N){
					pas=max(pas,ii);
				}
			}
		}
	}
	cout<<pas;
	return 0;
}

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