답안 #879622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879622	2023-11-27T18:41:33 Z	serifefedartar	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	102 ms	67928 KB

ho_t3

#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;

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]);
}

int 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 'int find_dist(int, int)':
ho_t3.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	67672 KB	Output is correct
2	Correct	13 ms	67672 KB	Output is correct
3	Correct	13 ms	67928 KB	Output is correct
4	Correct	13 ms	67824 KB	Output is correct
5	Correct	13 ms	67676 KB	Output is correct
6	Correct	14 ms	67724 KB	Output is correct
7	Correct	13 ms	67676 KB	Output is correct
8	Correct	13 ms	67672 KB	Output is correct
9	Correct	13 ms	67836 KB	Output is correct
10	Correct	14 ms	67672 KB	Output is correct
11	Correct	14 ms	67676 KB	Output is correct
12	Correct	13 ms	67844 KB	Output is correct
13	Correct	12 ms	67676 KB	Output is correct
14	Correct	13 ms	67804 KB	Output is correct
15	Correct	12 ms	67792 KB	Output is correct
16	Correct	13 ms	67672 KB	Output is correct
17	Correct	13 ms	67836 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	67672 KB	Output is correct
2	Correct	13 ms	67672 KB	Output is correct
3	Correct	13 ms	67928 KB	Output is correct
4	Correct	13 ms	67824 KB	Output is correct
5	Correct	13 ms	67676 KB	Output is correct
6	Correct	14 ms	67724 KB	Output is correct
7	Correct	13 ms	67676 KB	Output is correct
8	Correct	13 ms	67672 KB	Output is correct
9	Correct	13 ms	67836 KB	Output is correct
10	Correct	14 ms	67672 KB	Output is correct
11	Correct	14 ms	67676 KB	Output is correct
12	Correct	13 ms	67844 KB	Output is correct
13	Correct	12 ms	67676 KB	Output is correct
14	Correct	13 ms	67804 KB	Output is correct
15	Correct	12 ms	67792 KB	Output is correct
16	Correct	13 ms	67672 KB	Output is correct
17	Correct	13 ms	67836 KB	Output is correct
18	Correct	13 ms	67828 KB	Output is correct
19	Correct	13 ms	67800 KB	Output is correct
20	Correct	13 ms	67676 KB	Output is correct
21	Correct	13 ms	67672 KB	Output is correct
22	Correct	13 ms	67676 KB	Output is correct
23	Correct	13 ms	67672 KB	Output is correct
24	Correct	15 ms	67676 KB	Output is correct
25	Correct	13 ms	67672 KB	Output is correct
26	Correct	13 ms	67676 KB	Output is correct
27	Correct	13 ms	67840 KB	Output is correct
28	Correct	13 ms	67676 KB	Output is correct
29	Correct	14 ms	67676 KB	Output is correct
30	Correct	13 ms	67672 KB	Output is correct
31	Correct	13 ms	67676 KB	Output is correct
32	Correct	13 ms	67676 KB	Output is correct
33	Correct	13 ms	67676 KB	Output is correct
34	Correct	13 ms	67676 KB	Output is correct
35	Correct	13 ms	67820 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	67672 KB	Output is correct
2	Correct	13 ms	67672 KB	Output is correct
3	Correct	13 ms	67928 KB	Output is correct
4	Correct	13 ms	67824 KB	Output is correct
5	Correct	13 ms	67676 KB	Output is correct
6	Correct	14 ms	67724 KB	Output is correct
7	Correct	13 ms	67676 KB	Output is correct
8	Correct	13 ms	67672 KB	Output is correct
9	Correct	13 ms	67836 KB	Output is correct
10	Correct	14 ms	67672 KB	Output is correct
11	Correct	14 ms	67676 KB	Output is correct
12	Correct	13 ms	67844 KB	Output is correct
13	Correct	12 ms	67676 KB	Output is correct
14	Correct	13 ms	67804 KB	Output is correct
15	Correct	12 ms	67792 KB	Output is correct
16	Correct	13 ms	67672 KB	Output is correct
17	Correct	13 ms	67836 KB	Output is correct
18	Correct	102 ms	67872 KB	Output is correct
19	Correct	56 ms	67876 KB	Output is correct
20	Incorrect	32 ms	67868 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	67672 KB	Output is correct
2	Correct	13 ms	67672 KB	Output is correct
3	Correct	13 ms	67928 KB	Output is correct
4	Correct	13 ms	67824 KB	Output is correct
5	Correct	13 ms	67676 KB	Output is correct
6	Correct	14 ms	67724 KB	Output is correct
7	Correct	13 ms	67676 KB	Output is correct
8	Correct	13 ms	67672 KB	Output is correct
9	Correct	13 ms	67836 KB	Output is correct
10	Correct	14 ms	67672 KB	Output is correct
11	Correct	14 ms	67676 KB	Output is correct
12	Correct	13 ms	67844 KB	Output is correct
13	Correct	12 ms	67676 KB	Output is correct
14	Correct	13 ms	67804 KB	Output is correct
15	Correct	12 ms	67792 KB	Output is correct
16	Correct	13 ms	67672 KB	Output is correct
17	Correct	13 ms	67836 KB	Output is correct
18	Correct	13 ms	67828 KB	Output is correct
19	Correct	13 ms	67800 KB	Output is correct
20	Correct	13 ms	67676 KB	Output is correct
21	Correct	13 ms	67672 KB	Output is correct
22	Correct	13 ms	67676 KB	Output is correct
23	Correct	13 ms	67672 KB	Output is correct
24	Correct	15 ms	67676 KB	Output is correct
25	Correct	13 ms	67672 KB	Output is correct
26	Correct	13 ms	67676 KB	Output is correct
27	Correct	13 ms	67840 KB	Output is correct
28	Correct	13 ms	67676 KB	Output is correct
29	Correct	14 ms	67676 KB	Output is correct
30	Correct	13 ms	67672 KB	Output is correct
31	Correct	13 ms	67676 KB	Output is correct
32	Correct	13 ms	67676 KB	Output is correct
33	Correct	13 ms	67676 KB	Output is correct
34	Correct	13 ms	67676 KB	Output is correct
35	Correct	13 ms	67820 KB	Output is correct
36	Correct	102 ms	67872 KB	Output is correct
37	Correct	56 ms	67876 KB	Output is correct
38	Incorrect	32 ms	67868 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

답안 #879622

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