Submission #230117

#	Time	Username	Problem	Language	Result	Execution time	Memory
230117		AMO5	Collecting Stamps 3 (JOI20_ho_t3)	C++98	100 / 100	318 ms	509816 KiB

ho_t3

// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=404;

int dp[mxn][mxn][mxn][2]; //le,ri,cnt,where
int x[mxn],t[mxn],n,L;

int dist(int a, int b){
	if(a>b)swap(a,b);
	return min(b-a,L-(b-a));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	cin >> n >> L;
	for(int i=0; i<n; i++){
		cin >> x[i];
		x[i+n+1] = x[i];
	}
	for(int i=0; i<n; i++){
		cin >> t[i];
		t[i+n+1] = t[i];
	}
	for(int i=0; i<=2*n; i++)
		for(int j=0; j<=2*n; j++)
			for(int k=0; k<=n; k++)
				for(int l=0; l<2; l++)
					dp[i][j][k][l]=1e9+1;

	int ans = 0;
	dp[n][n][0][0]=0;
	for(int len=0; len<=n; len++){
		for(int i=n-len; i<=n; i++){
			 int j=i+len;
			 for(int k=0; k<=n; k++){
				 for(int l=0; l<2; l++){
					 if(dp[i][j][k][l]>1e9)continue;
					 int pos=(l==0?i:j);
					 ans=max(ans,k);
					 if(k==n)continue;
					 //left
					 if(i){
						 int cur=dp[i][j][k][l]+dist(x[pos],x[i-1]);
						 dp[i-1][j][k+(cur<=t[i-1])][0]=min(dp[i-1][j][k+(cur<=t[i-1])][0],cur);
					 }
					 //right
					 if(j<2*n){
						 int cur=dp[i][j][k][l]+dist(x[pos],x[j+1]);
						 dp[i][j+1][k+(cur<=t[j+1])][1]=min(dp[i][j+1][k+(cur<=t[j+1])][1],cur); 
					 }
				 }
			 }
		}
	}
	cout << ans << endl;
}	

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