| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 151802 | qkxwsm | Wombats (IOI13_wombats) | C++14 | 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.
// #include "wombats.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 5013
#define MAXM 213
#define DIP 1024
long long normalize(long long x, long long mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef array<array<int, MAXM>, MAXM> arr;
int N, M;
int H[MAXN][MAXM], V[MAXN][MAXM];
int pref[2][MAXM], opt[MAXM][MAXM];
map<int, arr> seg;
int cost(bool flag, int L, int R)
{
if (R < L)
{
swap(L, R);
}
return pref[flag][R] - pref[flag][L];
}
arr base(int idx)
{
arr res;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
res[i][j] = INF;
}
}
pref[0][0] = 0;
pref[1][0] = 0;
for (int j = 0; j < M - 1; j++)
{
pref[0][j + 1] = pref[0][j] + H[idx][j];
pref[1][j + 1] = pref[1][j] + H[idx + 1][j];
}
for (int i = 0; i < M; i++)
{
opt[i][M] = M - 1;
for (int j = M - 1; j >= 0; j--)
{
for (int k = (i ? opt[i - 1][j] : 0); k <= opt[i][j + 1]; k++)
{
int cur = cost(0, i, k) + cost(1, k, j) + V[idx][k];
if (cur < res[i][j])
{
opt[i][j] = k;
res[i][j] = cur;
}
}
}
}
// cerr << "moo\n";
// for (int i = 0; i < M; i++)
// {
// for (int j = 0; j < M; j++)
// {
// cerr << res[i][j] << ' ';
// }
// cerr << endl;
// }
return res;
}
arr comb(arr lt, arr rt)
{
arr res;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
res[i][j] = INF;
}
}
for (int i = 0; i < M; i++)
{
opt[i][M] = M - 1;
for (int j = M - 1; j >= 0; j--)
{
for (int k = (i ? opt[i - 1][j] : 0); k <= opt[i][j + 1]; k++)
{
int cur = lt[i][k] + rt[k][j];
if (cur < res[i][j])
{
res[i][j] = cur;
opt[i][j] = k;
}
}
}
}
return res;
}
void build(int w, int L, int R)
{
if (L == R)
{
seg[w] = base(L);
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
seg[w] = seg[w << 1];
if ((w << 1) > DIP)
{
seg.erase(w << 1);
}
build(w << 1 | 1, mid + 1, R);
seg[w] = comb(seg[w], seg[w << 1 | 1]);
if ((w << 1 | 1) > DIP)
{
seg.erase(w << 1 | 1);
}
}
void init(int R, int C, int h[5000][200], int v[5000][200])
{
for (int i = 0; i < MAXN; i++)
{
for (int j = 0; j < MAXM; j++)
{
H[i][j] = INF;
V[i][j] = INF;
}
}
N = R; M = C;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C - 1; j++)
{
H[i][j] = h[i][j];
}
}
for (int i = 0; i < R - 1; i++)
{
for (int j = 0; j < C; j++)
{
V[i][j] = v[i][j];
}
}
build(1, 0, N - 2);
}
void update(int w, int L, int R, int idx)
{
if ((idx < L || idx > R) && (w <= DIP))
{
return;
}
if (L == R)
{
// cerr << "pull " << L << endl;
seg[w] = base(L);
return;
}
int mid = (L + R) >> 1;
update(w << 1, L, mid, idx);
seg[w] = seg[w << 1];
if ((w << 1) > DIP)
{
seg.erase(w << 1);
}
update(w << 1 | 1, mid + 1, R, idx);
seg[w] = comb(seg[w], seg[w << 1 | 1]);
if ((w << 1 | 1) > DIP)
{
seg.erase(w << 1 | 1);
}
}
void changeH(int P, int Q, int W)
{
/* ... */
H[P][Q] = W;
if (P < N - 1) update(1, 0, N - 2, P);
if (P > 0) update(1, 0, N - 2, P - 1);
}
void changeV(int P, int Q, int W)
{
/* ... */
V[P][Q] = W;
update(1, 0, N - 2, P);
}
int escape(int V1, int V2)
{
return seg[1][V1][V2];
}