oj.uz

Submission #387994

# Submission time Handle Problem Language Result Execution time Memory
387994 2021-04-09T16:43:34 Z nikatamliani Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 13 ms 8308 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 505, oo = 1e18+10;
ll dp[N][N][2], save_dp[N][N][2], x[N], t[N];
ll n, s;
ll dist(ll i, ll j) {
	if(x[i] > x[j]) {
		swap(i, j);
	}
	return min(x[j] - x[i], x[i] + s - x[j]);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> s;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i];
	}
	for(int i = 1; i <= n; ++i) {
		cin >> t[i];
	}
	for(int i = n+2; i <= 2*n+1; ++i) {
		x[i] = x[i - n - 1];
		t[i] = t[i - n - 1];
	}
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			save_dp[i][j][0] = save_dp[i][j][1] = oo;
			dp[i][j][0] = dp[i][j][1] = oo;
		}
	}
	save_dp[n+1][n+1][0] = save_dp[n+1][n+1][1] = 0;
	ll ans = 0;
	auto mini = [](ll &x, ll y) {
		x = min(x, y);
	};
	for(int X = 2; X <= n+1; ++X) {
		for(int R = n+1; R <= 2*n+1; ++R) {
			for(int L = n+1; L >= R-n; --L) {
				ll &bestL = dp[L][R][0];
				ll &bestR = dp[L][R][1];
				if(L < n + 1) {
					ll opt0 = min(save_dp[L+1][R][0] + dist(L, L+1), save_dp[L+1][R][1] + dist(L, R));
					if(opt0 <= t[L]) mini(bestL, opt0);
					mini(bestL, dp[L+1][R][0] + dist(L, L+1));
					mini(bestL, dp[L+1][R][1] + dist(L, R));
				}
				if(R > n + 1) {
					ll opt0 = min(save_dp[L][R-1][1] + dist(R-1, R), save_dp[L][R-1][0] + dist(L, R));
					if(opt0 <= t[R]) mini(bestR, opt0);
					mini(bestR, dp[L][R-1][1] + dist(R-1, R));
					mini(bestR, dp[L][R-1][0] + dist(L, R));
				}
				if(bestL < oo || bestR < oo) {
					ans = X;
				}
			}
		}
		swap(dp, save_dp);
		for(int i = 0; i < N; ++i) {
			for(int j = 0; j < N; ++j) {
				for(int k = 0; k < 2; ++k) {
					dp[i][j][k] = oo;
				}
			}
		}
	}
	cout << ans-1 << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8268 KB Output is correct
2 Correct 9 ms 8268 KB Output is correct
3 Incorrect 13 ms 8308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8268 KB Output is correct
2 Correct 9 ms 8268 KB Output is correct
3 Incorrect 13 ms 8308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8268 KB Output is correct
2 Correct 9 ms 8268 KB Output is correct
3 Incorrect 13 ms 8308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8268 KB Output is correct
2 Correct 9 ms 8268 KB Output is correct
3 Incorrect 13 ms 8308 KB Output isn't correct
4 Halted 0 ms 0 KB -