| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1005924 | hotboy2703 | 웜뱃 (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.
#pragma once
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace WOMBAT{
ll ans[210];
ll R,C,H[5010][210],V[5010][210];
const ll SZ_TREE = 1024;
const ll INF = 1e9;
ll tree[SZ_TREE][210][210];
ll opt[210][210];
ll dp[210];
void solve(ll id,ll l,ll r){
for (ll st = 0;st < C;st ++){
dp[st] = 0;
for (ll j = st - 1;j >= 0;j --){
dp[j] = dp[j+1] + H[l][j];
}
for (ll j = st + 1;j < C;j ++){
dp[j] = dp[j-1] + H[l][j-1];
}
for (ll j = l + 1;j <= r + 1;j ++){
for (ll k = 0;k < C;k ++){
dp[k] += V[j-1][k];
}
for (ll k = 1;k < C;k ++){
dp[k] = min(dp[k],dp[k-1] + H[j][k-1]);
}
for (ll k = C - 2;k >= 0;k --){
dp[k] = min(dp[k],dp[k+1] + H[j][k]);
}
// for (ll k = 0;k < C;k ++){
// cout<<dp[k]<<' ';
// }
// cout<<'\n';
}
for (ll j = 0;j < C;j ++){
tree[id][st][j] = dp[j];
}
}
}
void reupdate(ll id){
for (ll st = 0;st < C;st ++){
for (ll en = C - 1;en >= 0;en--){
ll optl = (st == 0 ? 0 : opt[st-1][en]);
ll optr = (en == C - 1 ? C - 1 : opt[st][en+1]);
ll optmid = optl;
for (ll j = optl + 1;j <= optr; j++){
if (tree[id<<1][st][j] + tree[id<<1|1][j][en] < tree[id<<1][st][optmid] + tree[id<<1|1][optmid][en]){
optmid = j;
}
}
opt[st][en] = optmid;
tree[id][st][en] = tree[id<<1][st][optmid] + tree[id<<1|1][optmid][en];
}
}
}
void build(ll id,ll l,ll r){
if (l == r || id * 2 + 1 >= SZ_TREE){
solve(id,l,r);
return;
}
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
reupdate(id);
}
void update(ll id,ll l,ll r,ll i){
if (l == r || id * 2 + 1 >= SZ_TREE){
solve(id,l,r);
return;
}
ll mid = (l + r) >> 1;
update(id<<1,l,mid,i);
update(id<<1|1,mid+1,r,i);
reupdate(id);
}
}
void init(int R1, int C1, int H1[5000][200], int V1[5000][200]){
using namespace WOMBAT;
R = R1,C = C1;
for (ll i = 0;i < R;i ++){
for (ll j = 0;j < C - 1;j ++){
H[i][j] = H1[i][j];
}
}
for (ll i = 0;i < R - 1;i ++){
for (ll j = 0;j < C;j ++){
V[i][j] = V1[i][j];
}
}
build(1,0,R-2);
}
void changeH(int P, int Q, int W){
using namespace WOMBAT;
H[P][Q] = W;
update(1,0,R-2,P-1);
}
void changeV(int P, int Q, int W){
using namespace WOMBAT;
V[P][Q] = W;
update(1,0,R-2,P);
}
int escape(int V1, int V2){
using namespace WOMBAT;
return tree[1][V1][V2];
}