oj.uz

Submission #230103

# Submission time Handle Problem Language Result Execution time Memory
230103 2020-05-08T09:41:51 Z AMO5 Collecting Stamps 3 (JOI20_ho_t3) C++
0 / 100
 5 ms 896 KB 
// 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=201;

int dp[2*mxn][2*mxn][mxn][2]; //le,ri,cnt,where

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	ll L; cin >> L;
	ll x[n+n],t[n];
	for(int i=0; i<n; i++){
		cin >> x[i];
		x[i+n]=L+x[i];
	}
	for(int i=0; i<2*n; i++)
		for(int j=0; j<2*n; j++)
			for(int k=0; k<n; k++)
				dp[i][j][k][0]=1e9, dp[i][j][k][1]=1e9;
	
	for(int i=0; i<n; i++)cin >> t[i];
	int ans = 0;
	
	if(x[n]-L<=t[0])dp[n][n][1][0]=dp[n][n][1][1]=x[0];
	if(L-x[n-1]<=t[n-1])dp[n-1][n-1][1][0]=dp[n-1][n-1][1][1]=L-x[n-1];
	
	for(int k=1; k<n; k++){//cnt
		for(int i=0; i<n+n; i++){ //left
			for(int j=0; j<n+n; j++){ //right
			 	if(dp[i][j][k][0]!=1e9){
					//left to left
					for(int l=0; l<i; l++){
						ll cur = dp[i][j][k][0] + x[i] - x[l];
						if(cur<=t[(l)%n]){
							dp[l][j][k+1][0]=cur;
							ans = max(ans,k+1);
						}
					}
					//left to right
					for(int l=j+1; l<n+n; l++){
						ll cur = dp[i][j][k][0] + x[l] - x[i];
						if(cur<=t[(l)%n]){
							dp[i][l][k+1][1]=cur;
							ans = max(ans,k+1);
						}
					}
				}
				if(dp[i][j][k][1]!=1e9){
					//right to left
					for(int l=0; l<i; l++){
						ll cur = dp[i][j][k][1] + x[j] - x[l];
						if(cur<=t[(l)%n]){
							dp[l][j][k+1][0]=cur;
							ans = max(ans,k+1);
						}
					}
					//right to right
					for(int l=j+1; l<n+n; l++){					
						ll cur = dp[i][j][k][0] + x[l] - x[j];
						if(cur<=t[(l)%n]){
							dp[i][l][k+1][1]=cur;
							ans = max(ans,k+1);
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -