oj.uz

답안 #680932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680932 2023-01-12T04:06:19 Z TranGiaHuy1508 Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 40 ms 67736 KB 
#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

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

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

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

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