Submission #356179

#TimeUsernameProblemLanguageResultExecution timeMemory
356179mario05092929Wombats (IOI13_wombats)C++11
55 / 100
11804 ms39732 KiB
#include "wombats.h" #include <bits/stdc++.h> #define x first #define y second #define pb push_back #define all(v) v.begin(),v.end() #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; const int INF = 1e9; const int TMX = 1 << 18; const long long llINF = 1e18; const long long mod = 1e9+7; const long long hashmod = 100003; const int MAXN = 100000; const int MAXM = 1000000; typedef long long ll; typedef long double ld; typedef pair <int,int> pi; typedef pair <ll,ll> pl; typedef vector <int> vec; typedef vector <pi> vecpi; typedef long long ll; int n,m,sum,d[80][205][205],go[80][205][205],Lmin[205],Rmin[205]; int h[5005][205],v[5005][205],kn[205][205],opt[205][205]; int d2[205][205],dist[80][205][205],sq; int gmin[80],gmax[80],inc[5005]; void getDP(int g,int sy) { int st = gmin[g], en = gmax[g]; d2[st][sy] = 0; for(int i = sy-1;i >= 1;i--) d2[st][i] = d2[st][i+1]+h[st][i]; for(int i = sy+1;i <= m;i++) d2[st][i] = d2[st][i-1]+h[st][i-1]; for(int i = st+1;i <= en;i++) { Lmin[1] = d2[i-1][1]+v[i-1][1], Rmin[m] = d2[i-1][m]+v[i-1][m]; for(int j = 2;j <= m;j++) { Lmin[j] = min(d2[i-1][j]+v[i-1][j],Lmin[j-1]+h[i][j-1]); } for(int j = m-1;j >= 1;j--) { Rmin[j] = min(d2[i-1][j]+v[i-1][j],Rmin[j+1]+h[i][j]); } for(int j = 1;j <= m;j++) { d2[i][j] = min(Lmin[j],Rmin[j]); } } for(int i = 1;i <= m;i++) { dist[g][sy][i] = d2[en][i]; } } void Knuth(int g) { for(int i = 1;i <= m;i++) { kn[m][i] = INF*2; for(int j = 1;j <= m;j++) { if(kn[m][i] > d[g][m][j]+dist[g+1][j][i]) { opt[m][i] = j; kn[m][i] = d[g][m][j]+dist[g+1][j][i]; } } } for(int i = m-1;i >= 1;i--) { for(int j = 1;j <= m;j++) { kn[i][j] = INF*2; if(j == 1) { for(int k = 1;k <= m;k++) { if(kn[i][j] > d[g][i][k]+dist[g+1][k][j]) { opt[i][j] = k; kn[i][j] = d[g][i][k]+dist[g+1][k][j]; } } } else { for(int k = opt[i][j-1];k <= opt[i+1][j];k++) { if(kn[i][j] > d[g][i][k]+dist[g+1][k][j]) { opt[i][j] = k; kn[i][j] = d[g][i][k]+dist[g+1][k][j]; } } } } } for(int i = 1;i <= m;i++) { for(int j = 1;j <= m;j++) { d[g+1][i][j] = kn[i][j]; } } } void init(int R, int C, int H[5000][200], int V[5000][200]) { n = R, m = C; for(int i = 1;i <= n;i++) { for(int j = 1;j < m;j++) h[i][j] = H[i-1][j-1]; } for(int i = 1;i < n;i++) { for(int j = 1;j <= m;j++) v[i][j] = V[i-1][j-1]; } sq = sqrt(R); for(int g = 1;g <= sq;g++) { gmin[g] = (g-1)*sq+1; gmax[g] = g*sq+1; if(g == sq) gmax[g] = n; if(gmin[g] > gmax[g]) exit(-1); for(int i = gmin[g];i <= gmax[g];i++) inc[i] = g; for(int i = 1;i <= m;i++) { getDP(g,i); } } for(int i = 1;i <= m;i++) { for(int j = 1;j <= m;j++) { d[1][i][j] = dist[1][i][j]; } } for(int g = 1;g < sq;g++) { Knuth(g); } } void changeH(int x, int y, int val) { x++, y++; h[x][y] = val; int g = inc[x]; if(g < 1||g > sq) exit(-1); for(int i = 1;i <= m;i++) { getDP(g,i); } if(g != 1) { for(int i = 1;i <= m;i++) { getDP(g-1,i); } } if(g != sq) { for(int i = 1;i <= m;i++) { getDP(g+1,i); } } for(int i = 1;i <= m;i++) { for(int j = 1;j <= m;j++) { d[1][i][j] = dist[1][i][j]; } } for(int gg = 1;gg < sq;gg++) { Knuth(gg); } } void changeV(int x, int y, int val) { x++, y++; v[x][y] = val; int g = inc[x]; if(g < 1||g > sq) exit(-1); for(int i = 1;i <= m;i++) { getDP(g,i); } if(g != 1) { for(int i = 1;i <= m;i++) { getDP(g-1,i); } } if(g != sq) { for(int i = 1;i <= m;i++) { getDP(g+1,i); } } for(int i = 1;i <= m;i++) { for(int j = 1;j <= m;j++) { d[1][i][j] = dist[1][i][j]; } } for(int gg = 1;gg < sq;gg++) { Knuth(gg); } } int escape(int sy,int ey) { sy++, ey++; return d[sq][sy][ey]; }

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;
      |      ^~~
wombats.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
wombats.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
wombats.cpp:9: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      |
#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...