oj.uz

답안 #916336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916336 2024-01-25T17:03:35 Z EJIC_B_KEDAX Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using ll = long long;
#define int ll

using namespace std;

int32_t main() {
	int n, L;
	cin >> n >> L;
	vector<pair<int, int>> a(n + 2);
	a[0] = {0, INT64_MAX};
	a[n + 1] = {L, INT64_MAX};
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].y;
	}
	n += 2;
	vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(n, INT64_MAX / 2)));
	dp[0][n - 1][0] = 0;
	for (int l = n - 1; l > 0; l--) {
		for (int i = 0; i + l < n; i++) {
			int j = i + l;
			for (int s = 0; s < n; s++) {
				ll dist1 = a[i + 1].x - a[i].x, dist2 = a[i].x + L - a[j - 1].x;
				if (dp[i][j][s] + dist1 <= a[i + 1].y) {
					dp[i + 1][j][s + 1] = min(dp[i + 1][j][s + 1], dp[i][j][s] + dist1);
				} else {
					dp[i + 1][j][s] = min(dp[i + 1][j][s], dp[i][j][s] + dist1);
				}
				if (dp[i][j][s] + dist2 <= a[j - 1].y) {
					dp[j - 1][i][s + 1] = min(dp[j - 1][i][s + 1], dp[i][j][s] + dist2);
				} else {
					dp[j - 1][i][s] = min(dp[j - 1][i][s], dp[i][j][s] + dist2);
				}
			}
		}
		for (int i = l; i < n; i++) {
			int j = i - l;
			for (int s = 0; s < n; s++) {
				ll dist1 = a[i].x - a[i - 1].x, dist2 = L - a[i].x + a[j + 1].x;
				if (dp[i][j][s] + dist1 <= a[i - 1].y) {
					dp[i - 1][j][s + 1] = min(dp[i - 1][j][s + 1], dp[i][j][s] + dist1);
				} else {
					dp[i - 1][j][s] = min(dp[i - 1][j][s], dp[i][j][s] + dist1);
				}
				if (dp[i][j][s] + dist2 <= a[j + 1].y) {
					dp[j + 1][i][s + 1] = min(dp[j + 1][i][s + 1], dp[i][j][s] + dist2);
				} else {
					dp[j + 1][i][s] = min(dp[j + 1][i][s], dp[i][j][s] + dist2);
				}
			}
		}
	}
	for (int s = n - 1; s >= 0; s--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dp[i][j][s] < INT64_MAX / 2) {
					cout << s << '\n';
					return 0;
				}
			}
		}
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -