Submission #724705

#	Time	Username	Problem	Language	Result	Execution time	Memory
724705		vjudge1	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	4 ms	4472 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("shuffle.in","r",stdin);
    // freopen("shuffle.out","w",stdout);

	int n; ll l; cin >> n >> l;

	vector<ll> arr, tempo;
	for(int i=0;i<n;i++){
		ll x; cin >> x;
		arr.pb(x);
	}
	arr.pb(l);
	for(int i=0;i<n;i++) arr.pb(arr[i]+l);

	tempo.resize(2*n+1);
	for(int i=0;i<n;i++) cin >> tempo[i];
	for(int i=0;i<n;i++) tempo[i+n+1]=tempo[i];
	tempo[n]=-1;

	ll dp[25][25][405];
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=2*n;k++) 
				dp[i][j][k]=INF;
	dp[0][0][n]=0;

	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			for(int pos=0;pos<=2*n;pos++){
				if(dp[i][j][pos]==INF) continue;
				int nxd, nxu;

				if(pos>n){
					nxu=pos+1;
					nxd=nxu-i-2;
				}
				else{
					nxd=pos-1;
					nxu=nxd+i+2;
				}

				// cout << i << " " << pos << " " << nxd << " " << nxu << "\n";

				// if(j==3) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";

				ll curr=dp[i][j][pos]+abs(arr[pos]-arr[nxd]);
				if(nxd>=0 && tempo[nxd]>=curr){
					// if(j+1==5) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";
					ans=max(ans, j+1);
					dp[i+1][j+1][nxd]=min(dp[i+1][j+1][nxd], curr);
				}
				else if(nxd>=0) dp[i+1][j][nxd]=min(dp[i+1][j][nxd], curr);

				curr=dp[i][j][pos]+abs(arr[pos]-arr[nxu]);
				if(nxu<=2*n && tempo[nxu]>=curr){
					// if(j+1==5) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";
					ans=max(ans, j+1);
					dp[i+1][j+1][nxu]=min(dp[i+1][j+1][nxu], curr);
				}
				else if(nxu<=2*n) dp[i+1][j][nxu]=min(dp[i+1][j][nxu], curr);
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

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