제출 #733539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733539		pcc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	25 / 100	2016 ms	91392 KiB

ho_t3

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

#define ll long long
#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;

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;
	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(done[l][r][cnt][dir])continue;
		done[l][r][cnt][dir] = true;
		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(!done[l][nr][rcnt][1])pq.push(make_tuple(rt,l,nr,rcnt,1));
		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(!done[nl][r][lcnt][0])pq.push(make_tuple(lt,nl,r,lcnt,0));
	}
	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: 0 / 75