Submission #516181

#	Time	Username	Problem	Language	Result	Execution time	Memory
516181		inksamurai	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	153 ms	130636 KiB

ho_t3

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _34raRxL ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
void print(){cout<<"\n";}
template<class te,class ...ti>
void print(const te&v,const ti&...nv){cout<<v;if(sizeof...(nv)){cout<<" ";print(nv...);}}
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
//e

const ll inf=1e18;

ll dp[203][203][203][2];

void chmin(ll &a,ll b){
	a=min(a,b);
}

int main(){
_34raRxL;
	int n,l;
	cin>>n>>l;
	vi a(n),ts(n);
	{
		rep(i,n){
			cin>>a[i];
		}
		a.insert(a.begin(),0);
		a.pb(l);
		rep(i,n){
			cin>>ts[i];
		}	
		ts.insert(ts.begin(),0);
		n+=2;
	}
	rep(i,n)rep(j,n)rep(k,n){
		dp[i][j][k][0]=dp[i][j][k][1]=inf;
	}
	dp[0][n-1][0][0]=dp[0][n-1][0][1]=0;
	rep(i,n){
		drep(j,n){
			rep(k,n-1){
				ll vmi=inf,ad=0;
				if(i+1<j){
					vmi=min(dp[i][j][k][0]+a[i+1]-a[i],dp[i][j][k][1]+l-a[j]+a[i+1]);
					ad=(ts[i+1]>=vmi);
					chmin(dp[i+1][j][k+ad][0],vmi);
				}
				vmi=inf;
				if(j-1>i){
					vmi=min(dp[i][j][k][1]+a[j]-a[j-1],dp[i][j][k][0]+a[i]+l-a[j-1]);
					ad=(ts[j-1]>=vmi);
					chmin(dp[i][j-1][k+ad][1],vmi);
				}
			}
		}	
	}
	int ans=0;
	rep(i,n){
		rep(j,n){
			rep(k,n-1){
				if(dp[i][j][k][0]!=inf or dp[i][j][k][1]!=inf){
					ans=max(ans,k);
				}
			}
		}
	}
	print(ans,"\n");
//	
	return 0;
}

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