oj.uz

Submission #707549

# Submission time Handle Problem Language Result Execution time Memory
707549 2023-03-09T08:59:46 Z Dan4Life Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 521 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define int long long
#define sz(a) (int)a.size()
const int mxN = (int)4e2+10;
const int LINF = (int)2e18;
int dp[mxN][mxN][mxN][2];
int x[mxN], t[mxN];

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, L; cin >> n >> L; int ans = 0;
	for(int i = 1; i <= n; i++) cin >> x[i], x[n+i+1]=x[i], x[i]-=L;
	for(int i = 1; i <= n; i++) cin >> t[i], t[n+i+1]=t[i];
	for(int i = 0; i < mxN; i++)
		for(int j = 0; j < mxN; j++)
			for(int k = 0; k < mxN; k++)
				for(int l = 0; l < 2; l++)
					dp[i][j][k][l] = LINF;
	dp[n+1][n+1][0][0]=dp[n+1][n+1][0][1]=0;
	//0 1 2 3 4 5 6 0 1 2 3 4 5 6
	t[n+1] = -LINF;
	for(int len = 2; len <= n+1; len++){
		for(int l = 1; l <= n+1; l++){
			for(int k = 0; k <= n; k++){
				int r = l+len-1;
				dp[l][r][k][0] = min({ dp[l][r][k][0],
					dp[l+1][r][k][0]+min(abs(x[l+1]-x[l]),L-abs(x[l+1]-x[l])),
					dp[l+1][r][k][1]+min(abs(x[r]-x[l]),L-abs(x[r]-x[l]))
				});
				dp[l][r][k][1] = min({ dp[l][r][k][1],
					dp[l][r-1][k][0]+min(abs(x[l]-x[r]),L-abs(x[l]-x[r])),
					dp[l][r-1][k][1]+min(abs(x[r-1]-x[r]),L-abs(x[r-1]-x[r]))
				});
				if(k){
					int tm = abs(x[l+1]-x[l]); tm=min(tm,L-tm); tm+=dp[l+1][r][k-1][0];
					if(tm<=t[l]) dp[l][r][k][0] = min(dp[l][r][k][0], tm);
					tm = abs(x[r]-x[l]); tm=min(tm,L-tm); tm+=dp[l+1][r][k-1][1];
					if(tm<=t[l]) dp[l][r][k][0] = min(dp[l][r][k][0], tm);
					tm = abs(x[l]-x[r]); tm=min(tm,L-tm); tm+=dp[l][r-1][k-1][0];
					if(tm<=t[r]) dp[l][r][k][1] = min(dp[l][r][k][1],tm);
					tm = abs(x[r-1]-x[r]); tm=min(tm,L-tm); tm+=dp[l][r-1][k-1][1];
					if(tm<=t[r]) dp[l][r][k][1] = min(dp[l][r][k][1],tm);
				}
				if(len==n+1 and (dp[l][r][k][0]<LINF or dp[l][r][k][1]<LINF)) ans = max(ans, k);
			}
		}
	}

	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 521 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 521 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 521 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 521 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -