| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 437432 | RainAir | Wombats (IOI13_wombats) | C++11 | 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 <bits/stdc++.h>
#define fi first
#define se second
#define DB double
#define U unsigned
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5000 + 5;
const int MAXM = 200 + 5;
const int B = 16;
#define lc ((x)<<1)
#define rc ((x)<<1|1)
int n,m;
struct Matrix{
int a[MAXM][MAXM];// i列走到j列
Matrix(){CLR(a,0);}
Matrix operator * (const Matrix &t) const {
Matrix res;// res.a[i][j]= min(a[i][k]+t.a[k][j])
static int ps[MAXM][MAXM];FOR(i,0,m+1) FOR(j,0,m+1) ps[i][j] = -1;
FOR(l,1,m){
ROF(r,m,1){
// ps[l-1][r] <= ps[l][r] <= ps[l][r+1]
int ll = 1,rr = m;
if(ps[l-1][r] != -1) ll = ps[l-1][r];
if(ps[l][r+1] != -1) rr = ps[l][r+1];
res.a[l][r] = 1e9;
FOR(k,ll,rr){
if(res.a[l][r] > a[l][k]+t.a[k][r]){
res.a[l][r] = a[l][k]+t.a[k][r];
ps[l][r] = k;
}
}
}
}
return res;
}
}sm[1252];
int H[MAXN][MAXM],C[MAXN][MAXM];
inline Matrix gen(int i){
// 第 i 行
Matrix res;
FOR(l,1,m){
int sm = 0;
FOR(r,l,m){
res.a[l][r] = sm;
sm += H[i][r];
}
sm = 0;
ROF(r,l-1,1){
sm += H[i][r];
res.a[l][r] = sm;
}
}
FOR(l,1,m) FOR(r,1,m) res.a[l][r] += C[i][r];
return res;
}
inline Matrix rebuild(int x){
Matrix res=gen((x-1)*B+1);
FOR(i,(x-1)*B+2,std::min(n,x*B)) res = res*gen(i);
return res;
}
inline void build(int x,int l,int r){
if(l == r) return (void)(sm[x] = rebuild(l));
int mid = (l + r) >> 1;
build(lc,l,mid);build(rc,mid+1,r);
sm[x] = sm[lc]*sm[rc];
}
inline void update(int x,int l,int r,int p){
if(l == r) return (void)(sm[x] = rebuild(l));
int mid = (l + r) >> 1;
if(p <= mid) update(lc,l,mid,p);
else update(rc,mid+1,r,p);
sm[x] = sm[lc]*sm[rc];
}
int bel[MAXN];
inline void init(int RR,int CC,int h[5000][200],int c[5000][200]){
n = RR;m = CC;
FOR(i,1,n) FOR(j,1,m-1) H[i][j] = h[i-1][j-1];
FOR(i,1,n-1) FOR(j,1,m) C[i][j] = c[i-1][j-1];
FOR(i,1,n) bel[i] = (i-1)/B+1;
build(1,1,bel[n]);
}
inline void changeH(int p,int q,int w){
++p;++q;H[p][q] = w;
update(1,1,bel[n],bel[p]);
}
inline void changeV(int p,int q,int w){
++p;++q;C[p][q] = w;
update(1,1,bel[n],bel[p]);
}
inline int escape(int p,int q){
++p;++q;
return sm[1].a[p][q];
}