Submission #534566

#	Time	Username	Problem	Language	Result	Execution time	Memory
534566		alvingogo	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	82 ms	135308 KiB

ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
//#define int long long
using namespace std;

typedef long long ll;
const ll inf=2e16;
ll dp[205][205][205][2];
int main(){
	AquA;
	int n;
	ll l;
	cin >> n >> l;
	vector<ll> v(n+3),rv(n+3),t(n+3),rt(n+3);
	t[0]=rt[0]=4e9;
	rv[0]=l;
	v[0]=0;
	for(int i=1;i<=n;i++){
		cin >> v[i];
		rv[n-i+1]=v[i];
	}
	for(int i=1;i<=n;i++){
		cin >> t[i];
		rt[n-i+1]=t[i];
	}
	for(int i=0;i<205;i++){
		for(int j=0;j<205;j++){
			for(int k=0;k<205;k++){
				dp[i][j][k][0]=dp[i][j][k][1]=inf;
			}
		}
	}
	dp[0][0][0][0]=dp[0][0][0][1]=0;
	int maxx=0;
	for(int len=0;len<=n;len++){
		for(int i=0;i<=len;i++){
			int j=len-i;
			for(int k=0;k<=len;k++){
				ll z=dp[i][j][k][0];
				if(z!=inf){
					maxx=max(maxx,k);
				}
				if(z+v[i+1]-v[i]<=t[i+1]){
					dp[i+1][j][k+1][0]=min(dp[i+1][j][k+1][0],z+v[i+1]-v[i]);
				}
				else{
					dp[i+1][j][k][0]=min(dp[i+1][j][k][0],z+v[i+1]-v[i]);
				}
				if(z+v[i]-v[0]+rv[0]-rv[j+1]<=rt[j+1]){
					dp[i][j+1][k+1][1]=min(dp[i][j+1][k+1][1],z+v[i]-v[0]+rv[0]-rv[j+1]);
				}
				else{
					dp[i][j+1][k][1]=min(dp[i][j+1][k][1],z+v[i]-v[0]+rv[0]-rv[j+1]);
				}
				z=dp[i][j][k][1];
				if(z!=inf){
					maxx=max(maxx,k);
				}
				if(z+rv[j]-rv[j+1]<=rt[j+1]){
					dp[i][j+1][k+1][1]=min(dp[i][j+1][k+1][1],z+rv[j]-rv[j+1]);
				}
				else{
					dp[i][j+1][k][1]=min(dp[i][j+1][k][1],z+rv[j]-rv[j+1]);
				}
				if(z+rv[0]-rv[j]+v[i+1]-v[0]<=t[i+1]){
					dp[i+1][j][k+1][0]=min(dp[i+1][j][k+1][0],z+rv[0]-rv[j]+v[i+1]-v[0]);
				}
				else{
					dp[i+1][j][k][0]=min(dp[i+1][j][k][0],z+rv[0]-rv[j]+v[i+1]-v[0]);
				}
			}
		}
	}
	cout << maxx << "\n";
	return 0;
}

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