Submission #1031353

#TimeUsernameProblemLanguageResultExecution timeMemory
1031353tolbiWombats (IOI13_wombats)C++17
55 / 100
20057 ms27472 KiB
#include "wombats.h" #include <bits/stdc++.h> using namespace std; const int MAXR = 5003; const int MAXC = 203; const int INF = 1e9; constexpr int BLOK = 1000; int H[MAXR][MAXC]={},V[MAXR][MAXC]={}; int dp[(MAXR+BLOK-1)/BLOK*4][MAXC][MAXC]; int opt[MAXC][MAXC]; int cur[MAXC][MAXC]; int C,R,sz; void merge(int x){ if (x*2+1>=sz){ if (x-sz/2<(R+BLOK-1)/BLOK){ for (int i = 0; i < C; i++){ for (int j = 0; j < C; j++){ dp[x][i][j]=INF; } dp[x][i][i]=0; } for (int _ = (x-sz/2)*BLOK; _ < min(R,(x-sz/2+1)*BLOK); _++){ for (int i = 0; i < C; i++){ int somma = 0; for (int j = i; j < C; j++){ cur[i][j]=somma+V[_][j]; somma+=H[_][j]; } somma = 0; for (int j = i-1; j >= 0; j--){ somma+=H[_][j]; cur[i][j]=somma+V[_][j]; } } int edp[MAXC][MAXC]; for (int i = C-1; i >= 0; i--){ for (int j = 0; j < C; j++){ int lbound = 0; int rbound = C-1; if (j) lbound=opt[i][j-1]; if (i+1<C) rbound=opt[i+1][j]; edp[i][j]=dp[x][i][lbound]+cur[lbound][j]; opt[i][j]=lbound; for (int k = lbound; k <= rbound; k++){ if (dp[x][i][k]+cur[k][j]<edp[i][j]){ edp[i][j]=dp[x][i][k]+cur[k][j]; opt[i][j]=k; } } } } for (int i = 0; i < C; i++){ for (int j = 0; j < C; j++){ dp[x][i][j]=edp[i][j]; } } } } else { for (int i = 0; i < C; i++){ for (int j = 0; j < C; j++){ if (i==j) dp[x][i][j]=0; else dp[x][i][j]=INF; } } } } else { for (int i = C-1; i >= 0; i--){ for (int j = 0; j < C; j++){ int lbound = 0; int rbound = C-1; if (j) lbound=opt[i][j-1]; if (i+1<C) rbound=opt[i+1][j]; opt[i][j]=lbound; dp[x][i][j]=dp[x*2+1][i][lbound]+dp[x*2+2][lbound][j]; for (int k = lbound; k <= rbound; k++){ if (dp[x*2+1][i][k]+dp[x*2+2][k][j]<dp[x][i][j]){ dp[x][i][j]=dp[x*2+1][i][k]+dp[x*2+2][k][j]; opt[i][j]=k; } } } } } } void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) { C=CC,R=RR; sz=(1LL<<((int)(ceil(log2((R+BLOK-1)/BLOK)+1))))-1; for (int i = 0; i < R; i++){ for (int j = 0; j < C; j++){ if (j+1<C) H[i][j]=HH[i][j]; if (i+1<R) V[i][j]=VV[i][j]; } } for (int i = sz-1; i >= 0; i--){ merge(i); } } void changeH(int P, int Q, int W) { H[P][Q]=W; P/=BLOK; P+=sz/2; merge(P); while (P){ P=(P-1)/2; merge(P); } } void changeV(int P, int Q, int W) { V[P][Q]=W; P/=BLOK; P+=sz/2; merge(P); while (P){ P=(P-1)/2; merge(P); } } int escape(int V1, int V2) { return dp[0][V1][V2]; }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...