| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 389936 | rainboy | 미술 수업 (IOI13_artclass) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "wombats.h"
#include <string.h>
#define N 5000
#define M 200
#define M_ 313
#define N_ (1 << 4) /* N_ = pow2(ceil(log2(N - 1))) / M_ */
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int aa[N][M - 1], bb[N - 1][M], n, m, st[N_ * 2][M][M];
void pul(int i) {
int l = i << 1, r = l | 1, j1, j2, j3, x;
for (j1 = 0; j1 < m; j1++)
memset(st[i][j1], 0x3f, m * sizeof *st[i][j1]);
for (j1 = 0; j1 < m; j1++)
for (j2 = 0; j2 < m; j2++) {
int a = st[l][j1][j2];
if (a == INF)
continue;
for (j3 = 0; j3 < m; j3++)
if (st[i][j1][j3] > (x = a + st[r][j2][j3]))
st[i][j1][j3] = x;
}
}
void solve(int i_) {
int l = i_ * M_, r = min((i_ + 1) * M_, n - 1), i, j, js;
for (js = 0; js < m; js++) {
int *dp = st[N_ + i_][js], x;
if (l >= r)
memset(dp, 0x3f, m * sizeof *dp), dp[js] = 0;
else {
dp[js] = 0;
for (j = js + 1; j < m; j++)
dp[j] = dp[j - 1] + aa[l][j - 1];
for (j = js - 1; j >= 0; j--)
dp[j] = dp[j + 1] + aa[l][j];
for (i = l + 1; i <= r; i++) {
for (j = 0; j < m; j++)
dp[j] += bb[i - 1][j];
if (i < r || i == n - 1) {
for (j = 1; j < m; j++)
if (dp[j] > (x = dp[j - 1] + aa[i][j - 1]))
dp[j] = x;
for (j = m - 2; j >= 0; j--)
if (dp[j] > (x = dp[j + 1] + aa[i][j]))
dp[j] = x;
}
}
}
}
}
void init(int n_, int m_, int A[5000][200], int B[5000][200]) {
int i;
n = n_, m = m_;
for (i = 0; i < n; i++)
memcpy(aa[i], A[i], (m - 1) * sizeof *A[i]);
for (i = 0; i < n - 1; i++)
memcpy(bb[i], B[i], m * sizeof *B[i]);
for (i = 0; i < N_; i++)
solve(i);
for (i = N_ - 1; i > 0; i--)
pul(i);
}
void update(int i) {
solve(i), i += N_;
while (i > 1)
pul(i >>= 1);
}
void changeH(int i, int j, int w) {
aa[i][j] = w;
update(i % M_ == 0 && i == n - 1 ? i / M_ - 1 : i / M_);
}
void changeV(int i, int j, int w) {
bb[i][j] = w;
update(i / M_);
}
int escape(int js, int jt) {
return st[1][js][jt];
}