oj.uz

Submission #879632

# Submission time Handle Problem Language Result Execution time Memory
879632 2023-11-27T18:58:22 Z serifefedartar Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 53 ms 135260 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 + 100;
#define int long long

vector<int> X, T;
int dp[205][205][205][2], N, L;
int find_dist(int i, int j) {
	if (i != N + 1 && j != 0)
		return min(abs(X[j] - X[i]), L - abs(X[j] - X[i]));
	if (i == N + 1)
		return min(X[j], L - X[j]);
	if (j == 0)
		return min(X[i], L - X[i]);
}

signed main() {
	fast
	cin >> N >> L;

	X = vector<int>(N+1);
	T = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> X[i];
	for (int i = 1; i <= N; i++)
		cin >> T[i];

	for (int i = 0; i < 205; i++) {
		for (int j = 0; j < 205; j++) {
			for (int k = 0; k < 205; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = 1e9 + 1e8;
		}
	}
	
	dp[0][0][0][0] = dp[0][0][0][1] = 0;

	int ans = 0;
	for (int l = 0; l <= N; l++) {
		for (int r = 0; r <= N; r++) {
			if (l + r == N)
				continue;
			for (int cnt = 0; cnt <= N; cnt++) {
				// solda bulunuyor
				int x = dp[cnt][l][r][0] + find_dist(N - l + 1, N - l);
				if (x < dp[cnt + (x <= T[N-l])][l+1][r][0]) {
					dp[cnt + (x <= T[N-l])][l+1][r][0] = x;
					ans = max(ans, cnt + (x <= T[N-l]));
				}

				x = dp[cnt][l][r][0] + find_dist(N - l + 1, r + 1);
				if (x < dp[cnt + (x <= T[r+1])][l][r+1][1]) {
					dp[cnt + (x <= T[r+1])][l][r+1][1] = x;
					ans = max(ans, cnt + (x <= T[r+1]));
				}

				// sağda bulunuyor
				x = dp[cnt][l][r][1] + find_dist(N - l, r);
				if (x < dp[cnt + (x <= T[N-l])][l+1][r][0]) {
					dp[cnt + (x <= T[N-l])][l+1][r][0] = x;
					ans = max(ans, cnt + (x <= T[N-l]));
				}

				x = dp[cnt][l][r][1] + find_dist(r, r + 1);
				if (x < dp[cnt + (x <= T[r+1])][l][r+1][1]) {
					dp[cnt + (x <= T[r+1])][l][r+1][1] = x;
					ans = max(ans, cnt + (x <= T[r+1]));
				}
			}
		}
	}

	cout << ans << "\n";
}

Compilation message

ho_t3.cpp: In function 'long long int find_dist(long long int, long long int)':
ho_t3.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 135124 KB Output is correct
2 Correct 38 ms 135260 KB Output is correct
3 Correct 38 ms 135168 KB Output is correct
4 Correct 40 ms 135080 KB Output is correct
5 Correct 38 ms 135260 KB Output is correct
6 Correct 43 ms 135252 KB Output is correct
7 Correct 47 ms 135116 KB Output is correct
8 Correct 46 ms 135056 KB Output is correct
9 Correct 49 ms 135252 KB Output is correct
10 Correct 41 ms 135140 KB Output is correct
11 Correct 38 ms 135260 KB Output is correct
12 Correct 37 ms 135248 KB Output is correct
13 Correct 37 ms 135252 KB Output is correct
14 Correct 40 ms 135252 KB Output is correct
15 Correct 40 ms 135252 KB Output is correct
16 Incorrect 41 ms 135120 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 135124 KB Output is correct
2 Correct 38 ms 135260 KB Output is correct
3 Correct 38 ms 135168 KB Output is correct
4 Correct 40 ms 135080 KB Output is correct
5 Correct 38 ms 135260 KB Output is correct
6 Correct 43 ms 135252 KB Output is correct
7 Correct 47 ms 135116 KB Output is correct
8 Correct 46 ms 135056 KB Output is correct
9 Correct 49 ms 135252 KB Output is correct
10 Correct 41 ms 135140 KB Output is correct
11 Correct 38 ms 135260 KB Output is correct
12 Correct 37 ms 135248 KB Output is correct
13 Correct 37 ms 135252 KB Output is correct
14 Correct 40 ms 135252 KB Output is correct
15 Correct 40 ms 135252 KB Output is correct
16 Incorrect 41 ms 135120 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 135124 KB Output is correct
2 Correct 38 ms 135260 KB Output is correct
3 Correct 38 ms 135168 KB Output is correct
4 Correct 40 ms 135080 KB Output is correct
5 Correct 38 ms 135260 KB Output is correct
6 Correct 43 ms 135252 KB Output is correct
7 Correct 47 ms 135116 KB Output is correct
8 Correct 46 ms 135056 KB Output is correct
9 Correct 49 ms 135252 KB Output is correct
10 Correct 41 ms 135140 KB Output is correct
11 Correct 38 ms 135260 KB Output is correct
12 Correct 37 ms 135248 KB Output is correct
13 Correct 37 ms 135252 KB Output is correct
14 Correct 40 ms 135252 KB Output is correct
15 Correct 40 ms 135252 KB Output is correct
16 Incorrect 41 ms 135120 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 135124 KB Output is correct
2 Correct 38 ms 135260 KB Output is correct
3 Correct 38 ms 135168 KB Output is correct
4 Correct 40 ms 135080 KB Output is correct
5 Correct 38 ms 135260 KB Output is correct
6 Correct 43 ms 135252 KB Output is correct
7 Correct 47 ms 135116 KB Output is correct
8 Correct 46 ms 135056 KB Output is correct
9 Correct 49 ms 135252 KB Output is correct
10 Correct 41 ms 135140 KB Output is correct
11 Correct 38 ms 135260 KB Output is correct
12 Correct 37 ms 135248 KB Output is correct
13 Correct 37 ms 135252 KB Output is correct
14 Correct 40 ms 135252 KB Output is correct
15 Correct 40 ms 135252 KB Output is correct
16 Incorrect 41 ms 135120 KB Output isn't correct
17 Halted 0 ms 0 KB -