Submission #1286596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286596		WH8	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	109 ms	133324 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
void chmin(int & x, int v) {
	x=min(x, v);
}
signed main(){
	int n,m;cin>>n>>m;
	vector<int> x(n+4,0), t(n+4,0);
	for(int i=2;i<=n+1;i++)cin>>x[i];
	for(int i=2;i<=n+1;i++)cin>>t[i];
	int mem[n+4][n+4][n+4][2]; 
	for(int i=0;i<n+4;i++) for(int j=0;j<n+4;j++) for(int k=0;k<n+4;k++) mem[i][j][k][0]=mem[i][j][k][1]=1e15;
	mem[1][1][n+2][0]=mem[1][1][n+2][1]=0;
	auto dist=[&](int a, int b)->int{
		return min(m-abs(x[a]-x[b]), abs(x[a]-x[b]));
	};
	int ans=0;
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=n+2;j++){
			for(int k=n+2;k>j;k--){
				// right to right
				if(mem[i-1][j][k+1][1]+dist(k+1, k) <= t[k]) 
					chmin(mem[i][j][k][1], mem[i-1][j][k+1][1]+dist(k+1, k));
				chmin(mem[i][j][k][1],mem[i][j][k+1][1]+dist(k+1, k));
				//left to right
				if(mem[i-1][j][k+1][0]+dist(j, k)<=t[k])
					chmin(mem[i][j][k][1], mem[i-1][j][k+1][0]+dist(j,k));
				chmin(mem[i][j][k][1], mem[i][j][k+1][0]+dist(j, k));
				
				// left to left
				if(mem[i-1][j-1][k][0]+dist(j-1, j) <= t[j]) 
					chmin(mem[i][j][k][0], mem[i-1][j-1][k][0]+dist(j-1, j));
				chmin(mem[i][j][k][0], mem[i][j-1][k][0]+dist(j-1, j));
				// right to left
				if(mem[i-1][j-1][k][1]+dist(j, k)<=t[j])
					chmin(mem[i][j][k][0], mem[i-1][j-1][k][1]+dist(j, k));
				//~ if(i==3 and j==2 and k==4){
					//~ printf("coming from %lld, dist %lld\n", mem[i-1][j-1][k][1], dist(j, k));
				//~ }
				chmin(mem[i][j][k][0], mem[i][j-1][k][1]+dist(j, k));
				
				
				chmin(mem[i][j][k][1], mem[i][j][k][0]+dist(j, k));
				chmin(mem[i][j][k][0], mem[i][j][k][1]+dist(j, k));

				if(mem[i][j][k][0] < 1e12 or mem[i][j][k][1] < 1e12) ans=i;
				//~ printf("i %lld,  l(j) %lld, r(k) %lld, 0: %lld, 1: %lld\n", i,j,k,mem[i][j][k][0],mem[i][j][k][1]);
			}
		}
	}
	cout<<ans-1;
}	
/*

3 5 
1 2 3
1 2 3

4 10
1 2 8 9 
5 6 2 1 

6 10
1 2 3 4 5 
1 2 3 4 5 

6 87
9 23 44 62 67 78
15 91 53 91 89 46
*/

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