Submission #733545

#	Time	Username	Problem	Language	Result	Execution time	Memory
733545		pcc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	1457 ms	85596 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define ll int
#define pll pair<ll,ll>
#define fs first
#define sc second

const ll mxn = 202;
ll dp[mxn][mxn][mxn][2];
bool done[mxn][mxn][mxn][2];
pll arr[mxn];
priority_queue<tuple<ll,ll,ll,ll,ll>,vector<tuple<ll,ll,ll,ll,ll>>,greater<tuple<ll,ll,ll,ll,ll>>> pq;
ll n,L;
const ll inf = 1e9+10;

ll calc(ll s,ll e,ll dir){
	if(dir){
		return (e+L-s)%(L);
	}
	else{
		return L-(e+L-s)%L;
	}
}

void solve(){
	cin>>n>>L;
	for(int i = 1;i<=n;i++)cin>>arr[i].fs;
	for(int i = 1;i<=n;i++)cin>>arr[i].sc;
	for(auto &i:dp)for(auto &j:i)for(auto &k:j)for(auto &l:k)l = inf;
	arr[0] = {0,0};
	dp[0][0][0][0] = 0;
	pq.push(make_tuple(0,0,0,0,0));
	ll ans = 0;
	while(!pq.empty()){
		ll val = get<0>(pq.top()),l = get<1>(pq.top()),r = get<2>(pq.top());
		ll cnt = get<3>(pq.top()),dir = get<4>(pq.top());
		//cout<<val<<' '<<l<<' '<<r<<' '<<cnt<<' '<<dir<<endl;
		pq.pop();
		if(dp[l][r][cnt][dir] != val)continue;
		if((r+1)%(n+1) == l){
			ans = max(ans,cnt);
			continue;
		}
		ll pos = (dir?arr[r].fs:arr[l].fs);
		int nr = r+1;
		if(nr>=n+1)nr -= n+1;
		int nl = l-1;
		if(nl<0)nl += n+1;
		ll rt = val+calc(pos,arr[nr].fs,1);
		ll rcnt = cnt + (rt<=arr[nr].sc?1:0);
		if(dp[l][nr][rcnt][1] > rt)pq.push(make_tuple(rt,l,nr,rcnt,1)),dp[l][nr][rcnt][1] = rt;
		ll lt = val+calc(pos,arr[nl].fs,0);
		ll lcnt = cnt+(lt<=arr[nl].sc?1:0);
		//cout<<l<<','<<r<<','<<dir<<','<<pos<<lt<<','<<lcnt<<','<<','<<nl<<endl;
		if(dp[nl][r][lcnt][0] > lt)pq.push(make_tuple(lt,nl,r,lcnt,0)),dp[nl][r][lcnt][0] = lt;
	}
	cout<<ans;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	while(t--)solve();
}

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