Submission #255085

#	Time	Username	Problem	Language	Result	Execution time	Memory
255085		Goolakh	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	71 ms	72960 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math") 
 
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
 
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e2+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,L,X[maxn],T[maxn],dp[maxn][maxn][maxn][2],it,tt,ans=0;
void mst(ll &x,ll y){x=min(x,y);}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	memset(dp,69,sizeof(dp));
	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][0][0][0]=dp[0][0][1][0]=0;
	for(int b=0;b<=n;b++)for(int f=0;b+f<=n;f++)for(int k=0;k<=b+f;k++){
		it=dp[b][f][k][0];
		if(it<mod){ ans=max(ans,k);
			tt=it+X[f+1]-X[f];
			mst(dp[b][f+1][k+(tt<=T[f+1])][0],tt);
			tt=it+X[f]+L-X[n-b];
			mst(dp[b+1][f][k+(tt<=T[n-b])][1],tt);
		}
		it=dp[b][f][k][1];
		if(it<mod){ ans=max(ans,k);
			tt=it+X[n-b+1]-X[n-b];
			mst(dp[b+1][f][k+(tt<=T[n-b])][1],tt);
			tt=it+L-X[n-b+1]+X[f+1];
			mst(dp[b][f+1][k+(tt<=T[f+1])][0],tt);
		}
	}
	cout<<ans;
	
	return 0;
}

Compilation message (stderr)

ho_t3.cpp:19:58: warning: overflow in implicit constant conversion [-Woverflow]
 const ll maxn=2e2+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;
                                                          ^~~~

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