이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |