Submission #437439

#	Time	Username	Problem	Language	Result	Execution time	Memory
437439		RainAir	Wombats (IOI13_wombats)	C++11	100 / 100	7053 ms	236872 KiB

wombats

#include "wombats.h"
#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];

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]);
}

void changeH(int p,int q,int w){
	++p;++q;H[p][q] = w;
	update(1,1,bel[n],bel[p]);
}

void changeV(int p,int q,int w){
	++p;++q;C[p][q] = w;
	update(1,1,bel[n],bel[p]);
}

int escape(int p,int q){
	++p;++q;
	return sm[1].a[p][q];
}

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;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24