oj.uz

Submission #384644

# Submission time Handle Problem Language Result Execution time Memory
384644 2021-04-02T00:08:30 Z dapig Collecting Stamps 3 (JOI20_ho_t3) C++
15 / 100
 2000 ms 405228 KB 
#include <cstdio>
#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <utility>

using namespace std;

int ans = 0;
bool vis[400][400][2];
long long dp[400][400][201][2];
long long grid[400];
long long stamptime[400];

	int nums; long long len;
    int dplen, dp0len, dp00len;
	
void findans(int l, int r, int end) {
		if (vis[l][r][end]) return;
		vis[l][r][end] = true;
		if (l==r) {
			dp[l][l][0][end] = abs(len-grid[l]);
			if (abs(len-grid[l]) <= stamptime[l])
				dp[l][l][1][end] = abs(len-grid[l]);
		} else if (end == 0) {
			for (int i = l+1; i <= r; i++) {
				findans(i, r, 0); findans(i, r, 1);
				long distl = grid[i]-grid[l];
				long distr = grid[r]-grid[l];
				for (int j = 0; j < dp00len; j++) {
					if (dp[i][r][j][0]+distl <= stamptime[l]) {
						if (j != dp00len-1)
							dp[l][r][j+1][0] = min(dp[l][r][j+1][0],
									dp[i][r][j][0]+distl);
					} else
							dp[l][r][j][0] = min(dp[l][r][j][0],
									dp[i][r][j][0]+distl);
					if (dp[i][r][j][1]+distr <= stamptime[l]) {
						if (j != dp00len-1)
							dp[l][r][j+1][0] = min(dp[l][r][j+1][0],
									dp[i][r][j][1]+distr);
					} else
							dp[l][r][j][0] = min(dp[l][r][j][0],
									dp[i][r][j][1]+distr);
				}
				for (int j = dp00len-2; j >= 0; j--) {
					dp[l][r][j][0] = min(dp[l][r][j][0],
							dp[l][r][j+1][0]);
				}
			}
		} else {
			for (int i = r-1; i >= l; i--) {
				findans(l, i, 0); findans(l, i, 1);
				long distl = grid[r]-grid[l];
				long distr = grid[r]-grid[i];
				for (int j = 0; j < dp00len; j++) {
					if (dp[l][i][j][0]+distl <= stamptime[r]) {
						if (j != dp00len-1)
							dp[l][r][j+1][1] = min(dp[l][r][j+1][1],
									dp[l][i][j][0]+distl);
					} else
							dp[l][r][j][1] = min(dp[l][r][j][1],
									dp[l][i][j][0]+distl);
					if (dp[l][i][j][1]+distr <= stamptime[r]) {
						if (j != dp00len-1)
							dp[l][r][j+1][1] = min(dp[l][r][j+1][1],
									dp[l][i][j][1]+distr);
					} else
							dp[l][r][j][1] = min(dp[l][r][j][1],
									dp[l][i][j][1]+distr);
				}
				for (int j = dp00len-2; j >= 0; j--) {
					dp[l][r][j][1] = min(dp[l][r][j][1],
							dp[l][r][j+1][1]);
				}
			}
		}
		for (int i = 0; i < dp00len; i++) {
			if (dp[l][r][i][end] != (((long long) 2*1e9)*3)) {
				ans = max(ans, i);
			}
		}
	}

	int main() {

		cin >> nums >> len;
        dplen = nums*2; dp0len = nums*2; dp00len = nums+1;
		for (int i = 0; i < nums; i++) {
			int val; cin >> val;
			grid[i] = val; grid[nums+i] = val+len;
		}
		for (int i = 0; i < nums; i++) {
			int val; cin >> val;
			stamptime[i] = val; stamptime[nums+i] = val;
		}

		for (int i = 0; i < dplen; i++) {
			for (int j = 0; j < dp0len; j++) {
				for (int k = 0; k < dp00len; k++) {
					for (int l = 0; l < 2; l++) {
						dp[i][j][k][l] = ((long long) 2*1e9)*3;
					}
				}
			}
		}
		
		/*
		int sum = 0;
		for (int i = nums; i < grid.length; i++) {
			if (time[i] >= grid[i]-len) sum++;
			dp[nums][i][0] = new long[] {0, 0};
			for (int j = 1; j <= sum; j++) {
				dp[nums][i][j][1] = grid[i]-len;
				dp[nums][i][j][0] = (grid[i]-len)*2;
			}
			vis[nums][i] = new boolean[] {true, true};
		}
		sum = 0;
		for (int i = nums-1; i >= 0; i--) {
			if (time[i] >= len-grid[i]) sum++;
			dp[nums][i][0] = new long[] {0, 0};
			for (int j = 1; j <= sum; j++) {
				dp[i][nums-1][j][0] = len-grid[i];
				dp[i][nums-1][j][1] = (len-grid[i])*2;
			}
			vis[i][nums-1] = new boolean[] {true, true};
		}
		*/

		for (int i = 0; i <= nums; i++) {
			findans(i, i+nums-1, 0);
			findans(i, i+nums-1, 1);
		}
		cout << (ans) << "\n";

	}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1644 KB Output is correct
9 Correct 2 ms 2284 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 2284 KB Output is correct
13 Correct 2 ms 2284 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct
15 Correct 1 ms 1132 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 2 ms 2284 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1644 KB Output is correct
9 Correct 2 ms 2284 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 2284 KB Output is correct
13 Correct 2 ms 2284 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct
15 Correct 1 ms 1132 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 2 ms 2284 KB Output is correct
18 Correct 4 ms 2924 KB Output is correct
19 Correct 2 ms 1644 KB Output is correct
20 Correct 2 ms 2284 KB Output is correct
21 Correct 3 ms 2924 KB Output is correct
22 Correct 2 ms 1388 KB Output is correct
23 Correct 3 ms 3308 KB Output is correct
24 Correct 3 ms 2540 KB Output is correct
25 Correct 3 ms 2924 KB Output is correct
26 Correct 3 ms 2924 KB Output is correct
27 Correct 2 ms 1132 KB Output is correct
28 Correct 2 ms 1388 KB Output is correct
29 Correct 3 ms 3308 KB Output is correct
30 Correct 3 ms 3308 KB Output is correct
31 Correct 3 ms 2924 KB Output is correct
32 Correct 3 ms 2560 KB Output is correct
33 Correct 3 ms 3308 KB Output is correct
34 Correct 3 ms 3308 KB Output is correct
35 Correct 3 ms 3308 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1644 KB Output is correct
9 Correct 2 ms 2284 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 2284 KB Output is correct
13 Correct 2 ms 2284 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct
15 Correct 1 ms 1132 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 2 ms 2284 KB Output is correct
18 Execution timed out 2106 ms 405228 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1644 KB Output is correct
9 Correct 2 ms 2284 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 2284 KB Output is correct
13 Correct 2 ms 2284 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct
15 Correct 1 ms 1132 KB Output is correct
16 Correct 2 ms 2284 KB Output is correct
17 Correct 2 ms 2284 KB Output is correct
18 Correct 4 ms 2924 KB Output is correct
19 Correct 2 ms 1644 KB Output is correct
20 Correct 2 ms 2284 KB Output is correct
21 Correct 3 ms 2924 KB Output is correct
22 Correct 2 ms 1388 KB Output is correct
23 Correct 3 ms 3308 KB Output is correct
24 Correct 3 ms 2540 KB Output is correct
25 Correct 3 ms 2924 KB Output is correct
26 Correct 3 ms 2924 KB Output is correct
27 Correct 2 ms 1132 KB Output is correct
28 Correct 2 ms 1388 KB Output is correct
29 Correct 3 ms 3308 KB Output is correct
30 Correct 3 ms 3308 KB Output is correct
31 Correct 3 ms 2924 KB Output is correct
32 Correct 3 ms 2560 KB Output is correct
33 Correct 3 ms 3308 KB Output is correct
34 Correct 3 ms 3308 KB Output is correct
35 Correct 3 ms 3308 KB Output is correct
36 Execution timed out 2106 ms 405228 KB Time limit exceeded
37 Halted 0 ms 0 KB -