Submission #425380

#	Time	Username	Problem	Language	Result	Execution time	Memory
425380		frodakcin	Wombats (IOI13_wombats)	C++17	100 / 100	6198 ms	112020 KiB

wombats

#include "wombats.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}

const int MR = 5e3+10;
const int SM = 20;
const int MC = 2e2+10;

int R, C, B, H[5000][200], V[5000][200], st[1024][MC][MC], dp[MC], best[MC];
bool cur;

void compute_block(int n, int l, int r)
{
	for(int i=0;i<C;++i)
	{
		memset(dp, 0x3f, C*sizeof*dp);
		dp[i]=0;
		for(int j=l;j<r;++j)
		{
			for(int c=0;c+1<C;++c)
				ckmin(dp[c+1], dp[c]+H[j][c]);
			for(int c=C-1;c>0;--c)
				ckmin(dp[c-1], dp[c]+H[j][c-1]);
			if(j+1<R)
				for(int c=0;c<C;++c)
					dp[c] += V[j][c];
		}
		memcpy(st[n][i], dp, C*sizeof*dp);
	}
}

void merge(int x, int y, int z)
{
	memset(st[z], 0x3f, sizeof st[z]);
	memset(best, 0, C*sizeof*best);
	best[C]=C-1;
	/*
	for(int i=0;i<C;++i) for(int j=0;j<C;++j) for(int k=0;k<C;++k)
		ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]);
		*/
	for(int d=-C+1;d<C;++d)
		for(int i=std::max(0, -d), mi=(C-std::max(0, d));i<mi;++i)
		{
			int j=i+d;
			int tr=-1;
			for(int k=best[i];k<=best[i+1];++k)
				if(ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]))
					tr=k;
			best[i]=tr;
		}
}

void upd(int n, int l, int r, int q)
{
	if(r-l<=SM)
		compute_block(n, l, r);
	else
	{
		int m=l+(r-l)/2;
		if(q==-1 || q<m) upd(n<<1, l, m, q);
		if(q==-1 || m<=q) upd(n<<1|1, m, r, q);
		merge(n<<1, n<<1|1, n);
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
	::R=R;
	::C=C;
	memcpy(::H, H, sizeof ::H);
	memcpy(::V, V, sizeof ::V);
	upd(1, 0, R, -1);
}

void changeH(int P, int Q, int W) { // 500x tot
	H[P][Q]=W;
	upd(1, 0, R, P);
}

void changeV(int P, int Q, int W) { // 500x tot
	V[P][Q]=W;
	upd(1, 0, R, P);
}

int escape(int V1, int V2) { // 200000x
	//return mat[0][V1][V2];
	return st[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]
   15 |  int res;
      |      ^~~
wombats.cpp:7:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |            ^~~~
wombats.cpp:7:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |                           ^~~~
wombats.cpp:8:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |            ^~~~
wombats.cpp:8:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |                           ^~~~

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