Submission #680932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680932	2023-01-12T04:06:19 Z	TranGiaHuy1508	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	40 ms	67736 KB

ho_t3

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int inf = 1e9 + 100;

int n, L;
vector<int> dist[2];
vector<int> T;

int dp[205][205][205][2];

int f(int l, int r, int cnt, int lr){
	if (cnt < 0) return -1;
	if (dp[l][r][cnt][lr] > -2) return dp[l][r][cnt][lr];

	int res = inf;
	bool valid = false;

	if (lr == 0){
		if (l > 0){
			int prev1 = f(l-1, r, cnt-1, lr);
			int prev2 = f(l-1, r, cnt, lr);
			int d = dist[0][l] - dist[0][l-1];

			if (prev1 >= 0 && prev1 <= T[l] - d){
				valid = true;
				res = min(res, prev1 + d);
			}

			if (prev2 >= 0){
				valid = true;
				res = min(res, prev2 + d);
			}
		}
		if (l > 0){
			int prev1 = f(l-1, r, cnt-1, lr^1);
			int prev2 = f(l-1, r, cnt, lr^1);
			int d = dist[0][l] + dist[1][r];

			if (prev1 >= 0 && prev1 <= T[l] - d){
				valid = true;
				res = min(res, prev1 + d);
			}

			if (prev2 >= 0){
				valid = true;
				res = min(res, prev2 + d);
			}
		}
	}
	else{
		if (r < n+1){
			int prev1 = f(l, r+1, cnt-1, lr);
			int prev2 = f(l, r+1, cnt, lr);
			int d = dist[1][r] - dist[1][r+1];

			if (prev1 >= 0 && prev1 <= T[r] - d){
				valid = true;
				res = min(res, prev1 + d);
			}

			if (prev2 >= 0){
				valid = true;
				res = min(res, prev2 + d);
			}
		}
		if (r < n+1){
			int prev1 = f(l, r+1, cnt-1, lr^1);
			int prev2 = f(l, r+1, cnt, lr^1);
			int d = dist[0][l] + dist[1][r];

			if (prev1 >= 0 && prev1 <= T[r] - d){
				valid = true;
				res = min(res, prev1 + d);
			}

			if (prev2 >= 0){
				valid = true;
				res = min(res, prev2 + d);
			}
		}
	}

	if (!valid) res = -1;
	// if (res >= 0) cout << "dp[" << l << "][" << r << "][" << cnt << "][" << lr << "] = " << res << endl;
	return dp[l][r][cnt][lr] = res;
}

void main_program(){
	cin >> n >> L;

	dist[0].resize(n+2); dist[1].resize(n+2);

	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		dist[0][i] = x;
		dist[1][i] = L - x;
	}

	dist[0][0] = 0; dist[0][n+1] = L;
	dist[1][0] = L; dist[1][n+1] = 0;

	T.resize(n+2);
	for (int i = 1; i <= n; i++) cin >> T[i];

	T[0] = -1; T[n+1] = -1;

	for (int i = 0; i < 205; i++)
		for (int j = 0; j < 205; j++)
			for (int k = 0; k < 205; k++)
				for (int lr = 0; lr < 2; lr++)
					dp[i][j][k][lr] = -2;

	dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0;

	int res = 0;

	for (int i = 0; i <= n+1; i++){
		for (int j = 0; j <= n+1; j++){
			for (int k = 0; k <= n; k++){
				for (int lr = 0; lr < 2; lr++){
					if (f(i, j, k, lr) >= 0) res = max(res, k);
				}
			}
		}
	}

	cout << res << "\n";
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	67728 KB	Output is correct
2	Correct	35 ms	67704 KB	Output is correct
3	Correct	36 ms	67736 KB	Output is correct
4	Correct	37 ms	67664 KB	Output is correct
5	Correct	35 ms	67664 KB	Output is correct
6	Correct	33 ms	67644 KB	Output is correct
7	Correct	40 ms	67700 KB	Output is correct
8	Correct	35 ms	67728 KB	Output is correct
9	Correct	34 ms	67676 KB	Output is correct
10	Correct	34 ms	67688 KB	Output is correct
11	Correct	33 ms	67660 KB	Output is correct
12	Correct	34 ms	67640 KB	Output is correct
13	Correct	35 ms	67692 KB	Output is correct
14	Correct	38 ms	67660 KB	Output is correct
15	Correct	34 ms	67708 KB	Output is correct
16	Incorrect	36 ms	67660 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	67728 KB	Output is correct
2	Correct	35 ms	67704 KB	Output is correct
3	Correct	36 ms	67736 KB	Output is correct
4	Correct	37 ms	67664 KB	Output is correct
5	Correct	35 ms	67664 KB	Output is correct
6	Correct	33 ms	67644 KB	Output is correct
7	Correct	40 ms	67700 KB	Output is correct
8	Correct	35 ms	67728 KB	Output is correct
9	Correct	34 ms	67676 KB	Output is correct
10	Correct	34 ms	67688 KB	Output is correct
11	Correct	33 ms	67660 KB	Output is correct
12	Correct	34 ms	67640 KB	Output is correct
13	Correct	35 ms	67692 KB	Output is correct
14	Correct	38 ms	67660 KB	Output is correct
15	Correct	34 ms	67708 KB	Output is correct
16	Incorrect	36 ms	67660 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	67728 KB	Output is correct
2	Correct	35 ms	67704 KB	Output is correct
3	Correct	36 ms	67736 KB	Output is correct
4	Correct	37 ms	67664 KB	Output is correct
5	Correct	35 ms	67664 KB	Output is correct
6	Correct	33 ms	67644 KB	Output is correct
7	Correct	40 ms	67700 KB	Output is correct
8	Correct	35 ms	67728 KB	Output is correct
9	Correct	34 ms	67676 KB	Output is correct
10	Correct	34 ms	67688 KB	Output is correct
11	Correct	33 ms	67660 KB	Output is correct
12	Correct	34 ms	67640 KB	Output is correct
13	Correct	35 ms	67692 KB	Output is correct
14	Correct	38 ms	67660 KB	Output is correct
15	Correct	34 ms	67708 KB	Output is correct
16	Incorrect	36 ms	67660 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	67728 KB	Output is correct
2	Correct	35 ms	67704 KB	Output is correct
3	Correct	36 ms	67736 KB	Output is correct
4	Correct	37 ms	67664 KB	Output is correct
5	Correct	35 ms	67664 KB	Output is correct
6	Correct	33 ms	67644 KB	Output is correct
7	Correct	40 ms	67700 KB	Output is correct
8	Correct	35 ms	67728 KB	Output is correct
9	Correct	34 ms	67676 KB	Output is correct
10	Correct	34 ms	67688 KB	Output is correct
11	Correct	33 ms	67660 KB	Output is correct
12	Correct	34 ms	67640 KB	Output is correct
13	Correct	35 ms	67692 KB	Output is correct
14	Correct	38 ms	67660 KB	Output is correct
15	Correct	34 ms	67708 KB	Output is correct
16	Incorrect	36 ms	67660 KB	Output isn't correct
17	Halted	0 ms	0 KB	-