Submission #821672

#	Time	Username	Problem	Language	Result	Execution time	Memory
821672		vjudge1	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	77 ms	130776 KiB

ho_t3

#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
//#define ld long double
using namespace std;
using ll=long long;
const int inf = 1e18;
const int MN =205;
const int mod=1e9+7;
int n,L;
int x[MN],t[MN];
int dp[MN][MN][MN][2];
int dis(int a, int b) {
	return min(abs(x[a]-x[b]), L-abs(x[a]-x[b]));
}
void solve() {
	cin>>n>>L;
	for (int i=1; i<=n; i++) {
		cin>>x[i];
	}
//	cout<<dis(0,n)<<"\n";
	for (int i=1; i<=n; i++) {
		cin>>t[i];
	}
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			for (int k=0; k<=n; k++) {
				dp[i][j][k][0]=dp[i][j][k][1]=inf;
			}
		}
	}
	int ans=0;
	dp[0][0][0][0]=dp[0][0][0][1]=0;
	for (int i=0; i<=n; i++) {
		for (int j=0; j+i<=n; j++) {
			for (int k=0; k<=n; k++) {
				if(dp[i][j][k][0]!=inf) {
					ans=max(ans,k);
					int dist=dp[i][j][k][0]+dis(n-i+1,n-i);
					dp[i+1][j][k+(t[n-i]>=dist)][0]=min(dp[i+1][j][k+(t[n-i]>=dist)][0],dist);
					dist=dp[i][j][k][0]+dis(n-i+1,j+1);
					dp[i][j+1][k+(t[j+1]>=dist)][1]=min(dp[i][j+1][k+(t[j+1]>=dist)][1],dist); 
				}
				if(dp[i][j][k][1]!=inf) {
					ans=max(ans,k);
					int dist=dp[i][j][k][1]+dis(j,n-i);
					dp[i+1][j][k+(t[n-i]>=dist)][0]=min(dp[i+1][j][k+(t[n-i]>=dist)][0],dist);
					dist=dp[i][j][k][1]+dis(j,j+1);
					dp[i][j+1][k+(t[j+1]>=dist)][1]=min(dp[i][j+1][k+(t[j+1]>=dist)][1],dist); 
				}
			}
		}
	}
	cout<<ans;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}
		
}

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