oj.uz

Submission #551885

# Submission time Handle Problem Language Result Execution time Memory
551885 2022-04-21T19:35:52 Z LucaDantas Abduction 2 (JOI17_abduction2) C++17
27 / 100
 395 ms 63804 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2010, inf = 0x3f3f3f3f;

int A[maxn], B[maxn], R, C;

int find_first_A(int id, int val) { int i; for(i = id+1; A[i] < val; i++); return i; }
int find_first_B(int id, int val) { int i; for(i = id+1; B[i] < val; i++); return i; }

int find_last_A(int id, int val) { int i; for(i = id-1; A[i] < val; i--); return i; }
int find_last_B(int id, int val) { int i; for(i = id-1; B[i] < val; i--); return i; }

int find_first(int lim_id, int lim_val, bool k) { return k == 0 ? find_first_A(lim_id, lim_val) : find_first_B(lim_id, lim_val); }
int find_last(int lim_id, int lim_val, bool k) { return k == 0 ? find_last_A(lim_id, lim_val) : find_last_B(lim_id, lim_val); }

long long dp[maxn][maxn][2], cnt;
array<int,3> vis[maxn*maxn*2];

long long go(int r, int c, bool k) {
	if(dp[r][c][k] != -1)
		return dp[r][c][k];
	vis[cnt++] = {r, c, k};
	dp[r][c][k] = 0;
	int procurar = k == 0 ? r : c, eu = k == 0 ? c : r;
	int p1 = find_last(procurar, k == 0 ? B[eu] : A[eu], k), d1 = procurar - p1, v1 = k == 0 ? A[p1] : B[p1]; // ultimo cara vertical com indice menor que c e valor maior que A[r]
	int p2 = find_first(procurar, k == 0 ? B[eu] : A[eu], k), d2 = p2 - procurar, v2 = k == 0 ? A[p2] : B[p2]; // primeiro cara vertical com indice maior que c e valor maior que A[r]
	
	if(v1 > v2) // quero manter a invariante de que v1 < v2 pra ficar mais fácil de calcular as coisas
		swap(p1, p2), swap(d1, d2), swap(v1, v2);

	// subtraio 1 dos infinitos porque eu defini eles como o primeiro ponto fora do grid (0 ou R+1/C+1), então a distância deles fica 1 a mais doq pode
	if(v1 == inf)
		return dp[r][c][k] = max(d1, d2)-1; // cheguei ao fim indo pra algum dos lados, escolho o maior obviamente
	if(v2 == inf)
		return dp[r][c][k] = max(d1 + (k == 0 ? go(p1, c, 1) : go(r, p1, 0)), (long long) d2-1); // cheguei ao fim indo pro maior mas não cheguei indo pro menor, então pego o melhor entre os dois

	// brutao pq meu guloso ta dando errado
	return dp[r][c][k] = max((long long) d1 + (k == 0 ? go(p1, c, !k) : go(r, p1, !k)), (long long) d2 + (k == 0 ? go(p2, c, !k) : go(r, p2, !k)));

	/* int down = find_first(eu, v1, !k), dist_down = down - eu, v_down = k == 0 ? B[down] : A[down]; // primeiro cara abaixo de mim (row index > r) com valor > v1
	int up = find_last(eu, v1, !k), dist_up = eu - up, v_up = k == 0 ? B[up] : A[up];

	if(B[down] > B[up])
		swap(down, up), swap(dist_down, dist_up), swap(v_down, v_up); */

	/* if(B[down] < v2 || d1 >= d2) {
		// nesse caso ou o p1 tem algum vizinho melhor que o p2 ou eles tem os mesmo vizinhos mas se eu for pro p1 eu ando mais, entao vou pro p1
		return (long long) d1 + (k == 0 ? go(p1, c, !k) : go(r, p1, !k));
	}
	// nesse caso o p1 e o p2 tem os mesmo vizinhos mas o p2 é mais longe entao vou pra ele
	return (long long) d2 + (k == 0 ? go(p2, c, !k) : go(r, p2, !k)); */
}

int main() {
	int q; scanf("%d %d %d", &R, &C, &q);
	for(int i = 1; i <= R; i++)
		scanf("%d", &A[i]);
	for(int i = 1; i <= C; i++)
		scanf("%d", &B[i]);
	A[0] = A[R+1] = B[0] = B[C+1] = inf;
	memset(dp, -1, sizeof dp);
	while(q--) {
		int r, c; scanf("%d %d", &r, &c);
		// printf("%lld\n", go(r, c, 0));
		long long ans = go(r, c, 0);
		
		while(cnt > 0) {
			auto [r, c, k] = vis[--cnt];
			dp[r][c][k] = -1;
		}

		ans = max(ans, go(r, c, 1));
		while(cnt > 0) {
			auto [r, c, k] = vis[--cnt];
			dp[r][c][k] = -1;
		}
		
		printf("%lld\n", ans);
	}
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  int q; scanf("%d %d %d", &R, &C, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d", &B[i]);
      |   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   int r, c; scanf("%d %d", &r, &c);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63420 KB Output is correct
2 Correct 28 ms 63496 KB Output is correct
3 Correct 28 ms 63464 KB Output is correct
4 Correct 31 ms 63444 KB Output is correct
5 Correct 27 ms 63436 KB Output is correct
6 Correct 28 ms 63444 KB Output is correct
7 Correct 24 ms 63436 KB Output is correct
8 Correct 26 ms 63568 KB Output is correct
9 Correct 25 ms 63540 KB Output is correct
10 Correct 27 ms 63464 KB Output is correct
11 Correct 27 ms 63508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63420 KB Output is correct
2 Correct 28 ms 63496 KB Output is correct
3 Correct 28 ms 63464 KB Output is correct
4 Correct 31 ms 63444 KB Output is correct
5 Correct 27 ms 63436 KB Output is correct
6 Correct 28 ms 63444 KB Output is correct
7 Correct 24 ms 63436 KB Output is correct
8 Correct 26 ms 63568 KB Output is correct
9 Correct 25 ms 63540 KB Output is correct
10 Correct 27 ms 63464 KB Output is correct
11 Correct 27 ms 63508 KB Output is correct
12 Correct 27 ms 63484 KB Output is correct
13 Correct 26 ms 63456 KB Output is correct
14 Correct 26 ms 63532 KB Output is correct
15 Correct 25 ms 63572 KB Output is correct
16 Correct 25 ms 63508 KB Output is correct
17 Correct 25 ms 63536 KB Output is correct
18 Correct 27 ms 63592 KB Output is correct
19 Correct 33 ms 63572 KB Output is correct
20 Correct 39 ms 63664 KB Output is correct
21 Correct 34 ms 63672 KB Output is correct
22 Correct 33 ms 63740 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63420 KB Output is correct
2 Correct 28 ms 63496 KB Output is correct
3 Correct 28 ms 63464 KB Output is correct
4 Correct 31 ms 63444 KB Output is correct
5 Correct 27 ms 63436 KB Output is correct
6 Correct 28 ms 63444 KB Output is correct
7 Correct 24 ms 63436 KB Output is correct
8 Correct 26 ms 63568 KB Output is correct
9 Correct 25 ms 63540 KB Output is correct
10 Correct 27 ms 63464 KB Output is correct
11 Correct 27 ms 63508 KB Output is correct
12 Correct 27 ms 63484 KB Output is correct
13 Correct 26 ms 63456 KB Output is correct
14 Correct 26 ms 63532 KB Output is correct
15 Correct 25 ms 63572 KB Output is correct
16 Correct 25 ms 63508 KB Output is correct
17 Correct 25 ms 63536 KB Output is correct
18 Correct 27 ms 63592 KB Output is correct
19 Correct 33 ms 63572 KB Output is correct
20 Correct 39 ms 63664 KB Output is correct
21 Correct 34 ms 63672 KB Output is correct
22 Correct 33 ms 63740 KB Output is correct
23 Runtime error 4 ms 596 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63532 KB Output is correct
2 Correct 29 ms 63504 KB Output is correct
3 Correct 29 ms 63528 KB Output is correct
4 Correct 30 ms 63572 KB Output is correct
5 Correct 28 ms 63452 KB Output is correct
6 Correct 124 ms 63692 KB Output is correct
7 Correct 106 ms 63740 KB Output is correct
8 Correct 289 ms 63692 KB Output is correct
9 Correct 266 ms 63704 KB Output is correct
10 Correct 299 ms 63804 KB Output is correct
11 Correct 395 ms 63792 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63420 KB Output is correct
2 Correct 28 ms 63496 KB Output is correct
3 Correct 28 ms 63464 KB Output is correct
4 Correct 31 ms 63444 KB Output is correct
5 Correct 27 ms 63436 KB Output is correct
6 Correct 28 ms 63444 KB Output is correct
7 Correct 24 ms 63436 KB Output is correct
8 Correct 26 ms 63568 KB Output is correct
9 Correct 25 ms 63540 KB Output is correct
10 Correct 27 ms 63464 KB Output is correct
11 Correct 27 ms 63508 KB Output is correct
12 Correct 27 ms 63484 KB Output is correct
13 Correct 26 ms 63456 KB Output is correct
14 Correct 26 ms 63532 KB Output is correct
15 Correct 25 ms 63572 KB Output is correct
16 Correct 25 ms 63508 KB Output is correct
17 Correct 25 ms 63536 KB Output is correct
18 Correct 27 ms 63592 KB Output is correct
19 Correct 33 ms 63572 KB Output is correct
20 Correct 39 ms 63664 KB Output is correct
21 Correct 34 ms 63672 KB Output is correct
22 Correct 33 ms 63740 KB Output is correct
23 Runtime error 4 ms 596 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -