답안 #767461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767461	2023-06-26T19:26:52 Z	NK_	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	52 ms	45948 KB

ho_t3

// 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #767461

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 10.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 10.0

Subtask #4
0 / 75.0