Submission #569098

#	Time	Username	Problem	Language	Result	Execution time	Memory
569098		MateGiorbelidze	Collecting Stamps 3 (JOI20_ho_t3)	C++14	25 / 100	201 ms	258160 KiB

ho_t3

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert
 
 
const ll MXT = 2000000000000;
 
ll dp[201][201][201][2];
int32_t main () {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n , l; cin>>n>>l;
    
    ll a[n + 2],t[n + 2];
    
    for (int i = 1; i <= n; i++)
    	cin>>a[i];
    	
    for (int i = 1; i <= n; i++)	
    	cin>>t[i];
    	
    for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= n + 1; j++)
			for(int k = 0; k <= n + 1; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = MXT;
				
	dp[n + 1][0][0][0] = dp[n + 1][0][0][1] = 0;
	
	a[0] = 0 ;
	a[n + 1] = l;
	for(int i = n + 1; i > 1; i--){
		for (int j = 0; j <= i; j++) {
			for(int k = 0; k <= n; k++) {
				
				ll mn = dp[i][j][k][0] + a[j + 1] - a[j];
				mn = min(mn , dp[i][j][k][1] + l - a[i] + a[j + 1]);
				
				if (mn <= t[j + 1]) dp[i][j + 1][k + 1][0] = min(mn , dp[i][j + 1][k + 1][0]);
				else dp[i][j + 1][k][0] = min(mn , dp[i][j + 1][k][0]);
				
				mn = dp[i][j][k][0] + a[j] + l - a[i - 1];
				mn = min(mn , dp[i][j][k][1] - a[i - 1] + a[i]);
				
				if (mn <= t[i - 1]) dp[i - 1][j][k + 1][1] = min(mn , dp[i - 1][j][k + 1][1]);
				else dp[i - 1][j][k][1] = min(mn , dp[i - 1][j][k][1]);
			}
			
		}
	}
	ll ans = 0;
	
	for (int j = 0; j <= n; j++) {
		for (ll k = 1; k <= n; k++) {
			if(dp[j + 1][j][k][0] != MXT) ans = max(k, ans);
        	if(dp[j + 1][j][k][1] != MXT) ans = max(k, ans);
		}
	}	
	cout<<ans;			
}

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