Submission #227330

#	Time	Username	Problem	Language	Result	Execution time	Memory
227330		kig9981	Wombats (IOI13_wombats)	C++17	100 / 100	4005 ms	189696 KiB

wombats

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "wombats.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const int B=10, SZ=1<<9;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], P[200][200], md[SZ], D[200];
 
void set_md(int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) return;
	set_md(2*bit,s,m);
	set_md(2*bit+1,m+1,e);
	md[bit]=min((m+1)*B-1,N-1);
}
 
int get_cost(int h, int s, int e)
{
	if(s>e) swap(s,e);
	return PS[h][e]-PS[h][s];
}
 
void dijk(int b)
{
	for(int r=0;r<M;r++) {
		for(int i=0;i<B && b*B+i<N;i++) {
			if(i) {
				for(int j=0;j<M;j++) D[j]+=V[b*B+i-1][j];
			}
			else {
				for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
			}
			for(int j=1;j<M;j++) D[j]=min(D[j],D[j-1]+H[b*B+i][j-1]);
			for(int j=M-2;j>=0;j--) D[j]=min(D[j],D[j+1]+H[b*B+i][j]);
		}
		for(int j=0;j<M;j++) tree[SZ+b][r][j]=D[j];
	}
}
 
void combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		P[i][i]=0;
		for(int j=1;j<M;j++) if(tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i]>=tree[l][i][j]+V[md[p]][j]+tree[r][j][i]) P[i][i]=j;
		tree[p][i][i]=tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i];
	}
	for(int i=1;i<M;i++) for(int j=0;j+i<M;j++) {
		P[j][j+i]=P[j][j+i-1];
		P[j+i][j]=P[j+i-1][j];
		for(int k=P[j][j+i-1]+1;k<=P[j+1][j+i];k++) if(tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i]>=tree[l][j][k]+V[md[p]][k]+tree[r][k][j+i]) P[j][j+i]=k;
		for(int k=P[j+i-1][j]+1;k<=P[j+i][j+1];k++) if(tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][j]>=tree[l][j+i][k]+V[md[p]][k]+tree[r][k][j]) P[j+i][j]=k;
		tree[p][j][j+i]=tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i];
		tree[p][j+i][j]=tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][j];
	}
}
 
void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C; memset(tree,0x3f,sizeof(tree));
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) {
		::H[i][j]=H[i][j];
		PS[i][j+1]=PS[i][j]+H[i][j];
	}
	for(int i=0;i<N-1;i++) for(int j=0;j<M;j++) ::V[i][j]=V[i][j];
	for(int i=0;i<SZ;i++) {
		if(i*B<N) dijk(i);
		else for(int j=0;j<M;j++) tree[SZ+i][j][j]=0;
	}
	set_md();
	for(int i=SZ;--i;) combine(i,2*i,2*i+1);
}
 
void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	for(int j=0;j<M-1;j++) PS[P][j+1]=PS[P][j]+H[P][j];
	dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
int escape(int V1, int V2)
{
	return tree[1][V1][V2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  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