Submission #1157847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157847		Nurislam	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	137 ms	130244 KiB

ho_t3

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

const int N = 2e5+2, inf = 1e18;

int dp[204][204][204][2];

void solve(){
	int n, l;
	cin >> n >> l;
	vector<int> a(n+2), mt(n+2);
	a[0] = 0; a[n+1] = l;
	for(int i = 1; i <= n; i ++ )cin >> a[i];
	for(int i = 1; i <= n; i ++ )cin >> mt[i];
	
	for(int x = 0; x <= n; x ++ )
		for(int y = 0; y <= n; y ++ )
			for(int z = 0; z <= n; z ++ )
				for(int t = 0; t < 2; t ++ )
					dp[x][y][z][t] = inf;
	
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	
	auto po = [&](int y) -> int{
		return n+1 - y;
	};
	
	auto chmin = [&](int &a, const int &b) -> void{
		a = min(a, b);
		return;
	};
	
	int ans = 0;
	for(int z = 0; z < n; z ++ )
		for(int x = 0; x < n; x ++ )
			for(int y = 0; y + x < n; y ++ ){
				
				// t == 0;
				if(dp[x][y][z][0] != inf ) {
					int ntim = 0;
					
					// go further
					
					ntim = dp[x][y][z][0] + a[x + 1] - a[x];
					if(mt[x + 1] >= ntim) chmin( dp[x+1][y][z+1][0], ntim );
					chmin( dp[x+1][y][z][0], ntim );
					
					// go back
					
					ntim = dp[x][y][z][0] + a[x] + l - a[po(y + 1)];
					if(mt[po(y + 1)] >= ntim) chmin( dp[x][y+1][z+1][1], ntim );
					chmin( dp[x][y+1][z][1], ntim );
				}
				
				// t == 1;
				if(dp[x][y][z][1] != inf ) {
					int ntim = 0;
					
					// go further
					
					ntim = dp[x][y][z][1] + a[po(y)] - a[po(y+1)];
					if(mt[po(y + 1)] >= ntim) chmin( dp[x][y+1][z+1][1], ntim );
					chmin( dp[x][y+1][z][1], ntim);
					
					// go back
					
					ntim = dp[x][y][z][1] + l - a[po(y)] + a[x + 1];
					if(mt[x + 1] >= ntim) chmin( dp[x+1][y][z+1][0], ntim );
					chmin( dp[x+1][y][z][0], ntim );
					
				};
				
				
			}
	
	
	for(int z = 0; z <= n; z ++ )
		for(int x = 0; x <= n; x ++ )
			for(int y = 0; y <= n; y ++ )
				for(int t = 0; t < 2; t ++ )
					if(dp[x][y][z][t] != inf)ans = z;
	
	cout << ans << '\n';
	
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    };
}

 
 

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