oj.uz

Submission #410685

# Submission time Handle Problem Language Result Execution time Memory
410685 2021-05-23T11:20:57 Z ngpin04 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define int long long 
using namespace std;
const int N = 205;
const long long oo = 1e18;

long long dp[N][N][N][2];

int costl[N];
int costr[N];
int a[N];
int t[N];
int n,L;

template <typename T> 
bool mini(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> L;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> t[i];

	a[++n] = L;	
	for (int i = 0; i < n; i++)
		costr[i] = a[i + 1] - a[i];

	for (int i = 1; i <= n; i++)
		costl[i % n] = a[i] - a[i - 1];

	// for (int i = 0; i < n; i++)
	// 	cerr << costr[i] << " \n"[i == n - 1];

	// for (int i = 0; i < n; i++)
	// 	cerr << costl[i] << " \n"[i == n - 1];

	for (int l = 0; l < n; l++) 
	for (int r = 0; r < n; r++)
	for (int cnt = 0; cnt < n; cnt++)
	for (int side = 0; side < 2; side++) 
		dp[l][r][cnt][side] = oo;
	
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	for (int l = 0, cntl = n; cntl > 0; l = (l + n - 1) % n, cntl--) 
	for (int r = 0, cntr = cntl - 1; cntr > 0; r = (r + 1) % n, cntr--) 
	for (int cnt = 0; cnt < n; cnt++) 
	for (int side = 0; side < 2; side++) {
		long long cur = dp[l][r][cnt][side];
		if (cur == oo)
			continue;

		// cerr << l << " " << r << " " << cnt << " " << side << "\n";

		int add = a[r] + (L - a[l]);
		long long cost;

		cost = 1LL * (side == 0) * add + costr[r];
		int nxtr = (r + 1) % n;
		mini(dp[l][nxtr][cnt + (cur + cost <= t[nxtr])][1], cur + cost);

		cost = 1LL * (side == 1) * add + costl[l];
		int nxtl = (l + n - 1) % n;
		mini(dp[nxtl][r][cnt + (cur + cost <= t[nxtl])][0], cur + cost);
	}

	int ans = 0;
	for (int cnt = 0; cnt < n; cnt++)
	for (int l = 0; l < n; l++)
	for (int r = 0; r < n; r++) if (l != r)
	for (int side = 0; side < 2; side++)
		if (dp[l][r][cnt][side] < oo)
			ans = cnt;

	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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