Submission #388002

#	Time	Username	Problem	Language	Result	Execution time	Memory
388002		nikatamliani	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	313 ms	8396 KiB

ho_t3

#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];
	}
	x[n+1] = 0;
	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;
		}
	}
	for(int R = n+1; R <= 2*n+1; ++R) {
		for(int L = n+1; L >= R-n; --L) {
			save_dp[L][R][0] = dist(n+1, R) + dist(L, R);
			save_dp[L][R][1] = dist(n+1, L) + dist(L, R);
		}
	}
	ll ans = 0;
	auto mini = [](ll &x, ll y) {
		x = min(x, y);
	};
	for(int X = 1; X <= n; ++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 << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75