Submission #1068068

#TimeUsernameProblemLanguageResultExecution timeMemory
1068068sleepntsheepWombats (IOI13_wombats)C++17
55 / 100
20061 ms19068 KiB
#pragma GCC optimize("O3,unroll-loops") #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> using namespace std; #include "wombats.h" #ifndef ROW #define ROW 5000 #endif #define COL 200 constexpr int B = 300; constexpr int ROW_BY_B = (ROW / B) + 10; int r, c, h[ROW][COL], v[ROW + 1][COL]; int L[9999], R[9999], By[9999], a[ROW_BY_B][COL][COL], ans[COL][COL]; void calc(int blk) { for (int ii = 0; ii < c; ++ii) { static int dp[2][COL]; /* find answer for (V1, V2) where V1 = ii */ memset(dp[0], 63, sizeof dp[0]); dp[0][ii] = 0; int I = 0; for (int i = L[blk]; i <= R[blk]; ++i, I ^= 1) { int pre = 1e9, suf = 1e9; for (int j = 0; j < c; ++j) { pre = min(pre, dp[I][j] - h[i][j]); dp[I][j] = min(dp[I][j], h[i][j] + pre); } for (int j = c - 1; j >= 0; --j) { suf = min(suf, dp[I][j] + h[i][j]); dp[I][j] = min(dp[I][j], suf - h[i][j]); } for (int j = 0; j < c; ++j) dp[!I][j] = dp[I][j] + v[i][j]; } for (int jj = 0; jj < c; ++jj) a[blk][ii][jj] = dp[I][jj]; } } void merg(int up[COL][COL], int down[COL][COL], int out[COL][COL]) { static int buf[COL][COL]; for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) buf[i][j] = 1e9; for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) { for (int k = 0; k < c; ++k) buf[i][k] = min(buf[i][k], up[i][j] + down[j][k]); } for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) out[i][j] = buf[i][j]; } void CalcAns() { for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) ans[i][j] = a[0][i][j]; for (int i = 1; i * B < r; ++i) merg(ans, a[i], ans); } int outdated = 0; void changeH(int P, int Q, int W) { int dl = W - h[P][Q + 1] + h[P][Q]; for (int j = Q + 1; j < c; ++j) h[P][j] += dl; calc(By[P]); outdated = 1; } void changeV(int P, int Q, int W) { v[P][Q] = W; calc(By[P]); outdated = 1; } void init(int R, int C, int H[ROW][200], int V[ROW][200]) { r = R, c = C; for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j) v[i][j] = V[i][j]; for (int i = 0 ; i < r; ++i) { for (int j = 0; j + 1 < c; ++j) h[i][j + 1] = H[i][j]; for (int j = 0; j + 1 < c; ++j) h[i][j + 1] += h[i][j]; } for (int i = 0; i * B < r; ++i) { L[i] = i * B; ::R[i] = min(r - 1, i * B + B - 1); calc(i); for (int j = L[i]; j <= ::R[i]; ++j) By[j] = i; } outdated = 1; } int escape(int V1, int V2) { if (outdated) --outdated, CalcAns(); return ans[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...