oj.uz

Submission #767461

# Submission time Handle Problem Language Result Execution time Memory
767461 2023-06-26T19:26:52 Z NK_ Collecting Stamps 3 (JOI20_ho_t3) C++17
15 / 100
 52 ms 45948 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

template<class T> using V = vector<T>;

const int INF = 1e9+10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, L; cin >> N >> L;
	V<int> A(N), T(N);

	for(auto& x : A) cin >> x;
	for(auto& x : T) cin >> x;

	A.insert(begin(A), 0); T.insert(begin(T), -1);
	A.push_back(0); T.push_back(-1);

	// for(auto& x : A) cout << x << " ";
	// cout << endl;
	// for(auto& x : T) cout << x << " ";
	// cout << endl;

	// dp[SFX][PFX][K][2] = min time

	int dp[N + 1][N + 1][N + 1][2];
	for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) {
		for(int k = 0; k <= N; k++) for(int l = 0; l < 2; l++) {
			dp[i][j][k][l] = INF;
		}
	}

	int ans = 0;
	dp[0][0][0][0] = 0;
	for(int w = 0; w <= N; w++) {
		for(int s = 0; s <= N; s++) {
			int p = w - s; if (p < 0) continue;

			for(int k = 0; k <= N; k++) for(int x = 0; x < 2; x++) if (dp[s][p][k][x] != INF) {
				// cout << s << " " << p << " " << k << " " << x << " -> " << dp[s][p][k][x] << endl;
				ans = max(ans, k);
				
				int i = (x == 0 ? sz(A) - 1 - s : p);
				if (w+1 <= N) {
					// move left
					{
						int ni = (sz(A) - 1 - s - 1);
						int nt = dp[s][p][k][x] + min(L - abs(A[i] - A[ni]), abs(A[i] - A[ni]));
						// cout << "LEFT: " << nt << endl;
						int get = (T[ni] >= nt);
						dp[s+1][p][k + get][0] = min(dp[s+1][p][k + get][0], nt);
					}


					// move right
					{
						int ni = p + 1;
						int nt = dp[s][p][k][x] + min(L - abs(A[i] - A[ni]), abs(A[i] - A[ni]));
						// cout << "RIGHT: " << nt << endl;
						int get = (T[ni] >= nt);
						dp[s][p+1][k + get][1] = min(dp[s][i+1][k + get][1], nt);
					}
				}
			}
		}
	}

	cout << ans << nl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 216 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 216 KB Output is correct
32 Correct 1 ms 320 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 320 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 52 ms 45948 KB Output is correct
19 Correct 21 ms 21692 KB Output is correct
20 Correct 8 ms 8532 KB Output is correct
21 Correct 19 ms 20012 KB Output is correct
22 Correct 29 ms 29396 KB Output is correct
23 Correct 7 ms 6740 KB Output is correct
24 Correct 4 ms 4692 KB Output is correct
25 Correct 7 ms 6620 KB Output is correct
26 Correct 2 ms 1748 KB Output is correct
27 Correct 7 ms 6996 KB Output is correct
28 Correct 4 ms 4312 KB Output is correct
29 Incorrect 7 ms 7128 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 216 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 216 KB Output is correct
32 Correct 1 ms 320 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 320 KB Output is correct
36 Correct 52 ms 45948 KB Output is correct
37 Correct 21 ms 21692 KB Output is correct
38 Correct 8 ms 8532 KB Output is correct
39 Correct 19 ms 20012 KB Output is correct
40 Correct 29 ms 29396 KB Output is correct
41 Correct 7 ms 6740 KB Output is correct
42 Correct 4 ms 4692 KB Output is correct
43 Correct 7 ms 6620 KB Output is correct
44 Correct 2 ms 1748 KB Output is correct
45 Correct 7 ms 6996 KB Output is correct
46 Correct 4 ms 4312 KB Output is correct
47 Incorrect 7 ms 7128 KB Output isn't correct
48 Halted 0 ms 0 KB -