oj.uz

Submission #551884

# Submission time Handle Problem Language Result Execution time Memory
551884 2022-04-21T19:34:57 Z LucaDantas Abduction 2 (JOI17_abduction2) C++17
13 / 100
 109 ms 128820 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];

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 25 ms 63444 KB Output is correct
2 Correct 25 ms 63472 KB Output is correct
3 Correct 28 ms 63492 KB Output is correct
4 Correct 26 ms 63456 KB Output is correct
5 Correct 24 ms 63432 KB Output is correct
6 Correct 25 ms 63440 KB Output is correct
7 Correct 25 ms 63472 KB Output is correct
8 Correct 26 ms 63492 KB Output is correct
9 Correct 25 ms 63492 KB Output is correct
10 Correct 28 ms 63440 KB Output is correct
11 Correct 25 ms 63544 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 63444 KB Output is correct
2 Correct 25 ms 63472 KB Output is correct
3 Correct 28 ms 63492 KB Output is correct
4 Correct 26 ms 63456 KB Output is correct
5 Correct 24 ms 63432 KB Output is correct
6 Correct 25 ms 63440 KB Output is correct
7 Correct 25 ms 63472 KB Output is correct
8 Correct 26 ms 63492 KB Output is correct
9 Correct 25 ms 63492 KB Output is correct
10 Correct 28 ms 63440 KB Output is correct
11 Correct 25 ms 63544 KB Output is correct
12 Correct 26 ms 63548 KB Output is correct
13 Correct 27 ms 63820 KB Output is correct
14 Correct 25 ms 63484 KB Output is correct
15 Correct 25 ms 63564 KB Output is correct
16 Correct 25 ms 63568 KB Output is correct
17 Correct 26 ms 63544 KB Output is correct
18 Correct 26 ms 63580 KB Output is correct
19 Runtime error 81 ms 128776 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 63444 KB Output is correct
2 Correct 25 ms 63472 KB Output is correct
3 Correct 28 ms 63492 KB Output is correct
4 Correct 26 ms 63456 KB Output is correct
5 Correct 24 ms 63432 KB Output is correct
6 Correct 25 ms 63440 KB Output is correct
7 Correct 25 ms 63472 KB Output is correct
8 Correct 26 ms 63492 KB Output is correct
9 Correct 25 ms 63492 KB Output is correct
10 Correct 28 ms 63440 KB Output is correct
11 Correct 25 ms 63544 KB Output is correct
12 Correct 26 ms 63548 KB Output is correct
13 Correct 27 ms 63820 KB Output is correct
14 Correct 25 ms 63484 KB Output is correct
15 Correct 25 ms 63564 KB Output is correct
16 Correct 25 ms 63568 KB Output is correct
17 Correct 26 ms 63544 KB Output is correct
18 Correct 26 ms 63580 KB Output is correct
19 Runtime error 81 ms 128776 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63524 KB Output is correct
2 Correct 28 ms 63520 KB Output is correct
3 Correct 27 ms 63540 KB Output is correct
4 Correct 28 ms 63492 KB Output is correct
5 Correct 35 ms 63528 KB Output is correct
6 Correct 109 ms 63760 KB Output is correct
7 Correct 100 ms 63672 KB Output is correct
8 Runtime error 83 ms 128820 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 63444 KB Output is correct
2 Correct 25 ms 63472 KB Output is correct
3 Correct 28 ms 63492 KB Output is correct
4 Correct 26 ms 63456 KB Output is correct
5 Correct 24 ms 63432 KB Output is correct
6 Correct 25 ms 63440 KB Output is correct
7 Correct 25 ms 63472 KB Output is correct
8 Correct 26 ms 63492 KB Output is correct
9 Correct 25 ms 63492 KB Output is correct
10 Correct 28 ms 63440 KB Output is correct
11 Correct 25 ms 63544 KB Output is correct
12 Correct 26 ms 63548 KB Output is correct
13 Correct 27 ms 63820 KB Output is correct
14 Correct 25 ms 63484 KB Output is correct
15 Correct 25 ms 63564 KB Output is correct
16 Correct 25 ms 63568 KB Output is correct
17 Correct 26 ms 63544 KB Output is correct
18 Correct 26 ms 63580 KB Output is correct
19 Runtime error 81 ms 128776 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -