oj.uz

Submission #771982

# Submission time Handle Problem Language Result Execution time Memory
771982 2023-07-03T13:10:17 Z Trisanu_Das Collecting Stamps 3 (JOI20_ho_t3) C++17
100 / 100
 57 ms 132288 KB 
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n;
long long X[410], Left[410][410][410], Right[410][410][410], T[410], L;
int main() {
	int i, j, k;
	scanf("%d%lld", &n, &L);
	for (i = n + 1; i <= n + n; i++) scanf("%lld", &X[i]);
	for (i = n + 1; i <= n + n; i++) scanf("%lld", &T[i]);
	for (i = 0; i < n; i++) {
		X[i] = X[n + 1 + i] - L;
		T[i] = T[n + 1 + i];
	}
	for (i = n; i >= 0; i--) {
		for (j = n - i; j <= n; j++) {
			int b = j, e = j + i;
			for (k = 0; k <= n; k++)Left[b][e][k] = Right[b][e][k] = -1e18;
			Left[b][e][0] = Right[b][e][0] = 1e18;
			for (k = 1; k <= n - i; k++) {
				long long t1 = max(min(Left[b - 1][e][k - 1], T[b - 1]), Left[b - 1][e][k]) - (X[b] - X[b - 1]);
				long long t2 = max(min(Right[b][e + 1][k - 1], T[e + 1]), Right[b][e + 1][k]) - (X[e + 1] - X[b]);
				if (max(t1, t2) >= 0)Left[b][e][k] = max(t1, t2);
				t1 = max(min(Left[b - 1][e][k - 1], T[b - 1]), Left[b - 1][e][k]) - (X[e] - X[b - 1]);
				t2 = max(min(Right[b][e + 1][k - 1], T[e + 1]), Right[b][e + 1][k]) - (X[e + 1] - X[e]);
				if (max(t1, t2) >= 0)Right[b][e][k] = max(t1, t2);
			}
		}
	}
	int res = 0;
	for (i = 1; i <= n; i++)if (Left[n][n][i] >= 0 || Right[n][n][i]>=0)res = i;
	printf("%d\n", res);
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d%lld", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
ho_t3.cpp:10:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  for (i = n + 1; i <= n + n; i++) scanf("%lld", &X[i]);
      |                                   ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:11:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  for (i = n + 1; i <= n + n; i++) scanf("%lld", &T[i]);
      |                                   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 676 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 932 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 676 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 932 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 1068 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Correct 1 ms 1060 KB Output is correct
22 Correct 0 ms 680 KB Output is correct
23 Correct 1 ms 1192 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 1 ms 1108 KB Output is correct
26 Correct 1 ms 1108 KB Output is correct
27 Correct 1 ms 556 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 1236 KB Output is correct
30 Correct 1 ms 1236 KB Output is correct
31 Correct 1 ms 1060 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1192 KB Output is correct
34 Correct 1 ms 1236 KB Output is correct
35 Correct 1 ms 1192 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 676 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 932 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 47 ms 106316 KB Output is correct
19 Correct 25 ms 64716 KB Output is correct
20 Correct 13 ms 34688 KB Output is correct
21 Correct 24 ms 61072 KB Output is correct
22 Correct 32 ms 79064 KB Output is correct
23 Correct 12 ms 29604 KB Output is correct
24 Correct 9 ms 23232 KB Output is correct
25 Correct 12 ms 28968 KB Output is correct
26 Correct 4 ms 11220 KB Output is correct
27 Correct 12 ms 30208 KB Output is correct
28 Correct 9 ms 21588 KB Output is correct
29 Correct 12 ms 30856 KB Output is correct
30 Correct 10 ms 24376 KB Output is correct
31 Correct 12 ms 29064 KB Output is correct
32 Correct 6 ms 15324 KB Output is correct
33 Correct 13 ms 29012 KB Output is correct
34 Correct 4 ms 10580 KB Output is correct
35 Correct 11 ms 28372 KB Output is correct
36 Correct 5 ms 13708 KB Output is correct
37 Correct 12 ms 30164 KB Output is correct
38 Correct 7 ms 16680 KB Output is correct
39 Correct 12 ms 31444 KB Output is correct
40 Correct 7 ms 18644 KB Output is correct
41 Correct 55 ms 130980 KB Output is correct
42 Correct 36 ms 88456 KB Output is correct
43 Correct 52 ms 131020 KB Output is correct
44 Correct 35 ms 87424 KB Output is correct
45 Correct 53 ms 131092 KB Output is correct
46 Correct 36 ms 88456 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 676 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 932 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 1068 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Correct 1 ms 1060 KB Output is correct
22 Correct 0 ms 680 KB Output is correct
23 Correct 1 ms 1192 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 1 ms 1108 KB Output is correct
26 Correct 1 ms 1108 KB Output is correct
27 Correct 1 ms 556 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 1236 KB Output is correct
30 Correct 1 ms 1236 KB Output is correct
31 Correct 1 ms 1060 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1192 KB Output is correct
34 Correct 1 ms 1236 KB Output is correct
35 Correct 1 ms 1192 KB Output is correct
36 Correct 47 ms 106316 KB Output is correct
37 Correct 25 ms 64716 KB Output is correct
38 Correct 13 ms 34688 KB Output is correct
39 Correct 24 ms 61072 KB Output is correct
40 Correct 32 ms 79064 KB Output is correct
41 Correct 12 ms 29604 KB Output is correct
42 Correct 9 ms 23232 KB Output is correct
43 Correct 12 ms 28968 KB Output is correct
44 Correct 4 ms 11220 KB Output is correct
45 Correct 12 ms 30208 KB Output is correct
46 Correct 9 ms 21588 KB Output is correct
47 Correct 12 ms 30856 KB Output is correct
48 Correct 10 ms 24376 KB Output is correct
49 Correct 12 ms 29064 KB Output is correct
50 Correct 6 ms 15324 KB Output is correct
51 Correct 13 ms 29012 KB Output is correct
52 Correct 4 ms 10580 KB Output is correct
53 Correct 11 ms 28372 KB Output is correct
54 Correct 5 ms 13708 KB Output is correct
55 Correct 12 ms 30164 KB Output is correct
56 Correct 7 ms 16680 KB Output is correct
57 Correct 12 ms 31444 KB Output is correct
58 Correct 7 ms 18644 KB Output is correct
59 Correct 55 ms 130980 KB Output is correct
60 Correct 36 ms 88456 KB Output is correct
61 Correct 52 ms 131020 KB Output is correct
62 Correct 35 ms 87424 KB Output is correct
63 Correct 53 ms 131092 KB Output is correct
64 Correct 36 ms 88456 KB Output is correct
65 Correct 47 ms 118288 KB Output is correct
66 Correct 48 ms 108676 KB Output is correct
67 Correct 45 ms 103940 KB Output is correct
68 Correct 50 ms 96064 KB Output is correct
69 Correct 47 ms 117128 KB Output is correct
70 Correct 48 ms 112204 KB Output is correct
71 Correct 45 ms 113448 KB Output is correct
72 Correct 46 ms 114600 KB Output is correct
73 Correct 43 ms 106244 KB Output is correct
74 Correct 39 ms 99360 KB Output is correct
75 Correct 44 ms 109788 KB Output is correct
76 Correct 50 ms 125772 KB Output is correct
77 Correct 49 ms 125824 KB Output is correct
78 Correct 38 ms 97136 KB Output is correct
79 Correct 44 ms 100672 KB Output is correct
80 Correct 57 ms 123340 KB Output is correct
81 Correct 40 ms 101664 KB Output is correct
82 Correct 45 ms 107444 KB Output is correct
83 Correct 52 ms 130992 KB Output is correct
84 Correct 46 ms 112212 KB Output is correct
85 Correct 48 ms 122028 KB Output is correct
86 Correct 48 ms 119552 KB Output is correct
87 Correct 46 ms 109856 KB Output is correct
88 Correct 54 ms 132288 KB Output is correct
89 Correct 52 ms 132196 KB Output is correct
90 Correct 44 ms 110972 KB Output is correct
91 Correct 52 ms 132192 KB Output is correct
92 Correct 53 ms 132264 KB Output is correct
93 Correct 52 ms 129612 KB Output is correct