oj.uz

Submission #569083

# Submission time Handle Problem Language Result Execution time Memory
569083 2022-05-26T15:35:21 Z MateGiorbelidze Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 852 KB 
#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[205][205][205][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 = 1; j <= n; j++) {
		for (ll k = 1; k <= n; k++) {
			//cout<<dp[j][j][k][0]<<" "<<dp[j][j][k][1]<<" "<<k<<" "<<j<<'\n';
			if(dp[j][j][k][0] != MXT) ans = max(k, ans);
        	if(dp[j][j][k][1] != MXT) ans = max(k, ans);
		}
	}	
	cout<<ans;			
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -