제출 #551934

#제출 시각아이디문제언어결과실행 시간메모리
551934LucaDantas유괴 2 (JOI17_abduction2)C++17
100 / 100
2135 ms131112 KiB
// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...