제출 #551934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551934		LucaDantas	유괴 2 (JOI17_abduction2)	C++17	100 / 100	2135 ms	131112 KiB

abduction2

// Eu tinha codado isso pq achei que um guloso funcionava mas depois so mudei pra ser um brutao, dei umas otimizadas pra ser mais inteligente
// e magicamente passou full porque aparentemente o espaço da busca da DP é pequeno então ele não passa por tantos estados e no fim
// fica rapido kkkkkkkkkkkkkkkkkkkkkkkkkkk
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 50010, inf = 0x3f3f3f3f;

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

// Nem otimizei esses negocios aqui que eu ia colocar um binary lifting ou uma sparse table e nem precisou wtf KKKKKKKKK
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; }

// e vai ficar assim me desculpa, se n precisa n vou codar
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); }

map<int, long long> dp[maxn][2];

// Perdão esse código não foi feito pra ser compreensível e sim pra ser o mais enxuto possível pra eu conseguir codar rápido
// ficou muito feio porque como é num grid e eu tenho q ficar alternando sempre entre linha e coluna eu preferi colocar uma variavel
// e escolher cada coisa individualmente de acordo com o k (por isso tantos operadores ternarios) ao inves de fazer um bloco inteiro
// pra k == 0 e outro pra k == 1

long long go(int r, int c, bool k) {
	if(dp[r][k].count(c))
		return dp[r][k][c];

	int procurar = k == 0 ? r : c, eu = k == 0 ? c : r;

	// k == 0 eu sou uma coluna e estou procurando a proxima linha que eu vou visitar
	// k == 1, o oposto de k == 0
	
	// p{1/2} == indice do cara que eu achei, d{1/2} == distancia, v{1/2} == valor do cara que eu achei
	int p1 = find_last(procurar, k == 0 ? B[eu] : A[eu], k); // ultimo cara com sentido oposto com indice < procurar e valor > A[r]
	int d1 = procurar - p1, v1 = k == 0 ? A[p1] : B[p1];
	
	int p2 = find_first(procurar, k == 0 ? B[eu] : A[eu], k); // primeiro cara com sentido oposto com indice > procurar e valor > A[r]
	int d2 = p2 - procurar, v2 = k == 0 ? A[p2] : B[p2];
	
	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 do que é pra ser
	if(v1 == inf)
		return dp[r][k][c] = max(d1, d2)-1; // cheguei ao fim indo pra algum dos lados, escolho o maior obviamente
	if(v2 == inf)
		return dp[r][k][c] = 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

	// ahh, que linha linda!
	// return dp[r][k][c] = 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)));

	// vou ser bonzinho e deixar mais legível
	long long goP1 = (long long) d1 + (k == 0 ? go(p1, c, !k) : go(r, p1, !k)); // se eu for pro p1
	long long goP2 = (long long) d2 + (k == 0 ? go(p2, c, !k) : go(r, p2, !k)); // se eu for pro p2
	// ainda tá feio por causa do case work com k mas ta melhor

	return dp[r][k][c] = max(goP1, goP2);
}

// olhando essa main o problema parece tão bonito... ;-;
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;
	while(q--) {
		int r, c; scanf("%d %d", &r, &c);
		printf("%lld\n", max(go(r, c, 0), go(r, c, 1)));
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56