제출 #425381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425381		frodakcin	웜뱃 (IOI13_wombats)	C++17	55 / 100	20031 ms	18468 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 ML = 500;
const int MB = 55;
const int MC = 2e2+10;

int R, C, B, H[5000][200], V[5000][200], ans[2][MC][MC], dp[MC], bl[MB], br[MB], best[MC];
bool cur;
int mat[MB][MC][MC];

void compute_block(int b)
{
	for(int i=0;i<C;++i)
	{
		memset(dp, 0x3f, C*sizeof*dp);
		dp[i]=0;
		for(int j=bl[b];j<br[b];++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(mat[b][i], dp, C*sizeof*dp);
	}
}

void compute_ans()
{
	cur = 0;
	memset(ans, 0x3f, sizeof ans);
	for(int i=0;i<C;++i)
		ans[cur][i][i]=0;
	for(int b=0;b<B;++b)
	{
		cur ^= 1;
		memset(ans[cur], 0x3f, sizeof ans[cur]);
		memset(best, 0, C*sizeof*best);
		best[C]=C-1;
		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(ans[cur][i][j], ans[!cur][i][k]+mat[b][k][j]))
						tr=k;
				best[i]=tr;
			}
	}
}

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

	for(int i=0;i<R;i += ML)
	{
		bl[B]=i;
		br[B]=std::min(i+ML, R);
		compute_block(B);
		++B;
	}
	compute_ans();
}

void changeH(int P, int Q, int W) { // 500x tot
	H[P][Q]=W;
	compute_block(P/ML);
	compute_ans();
}

void changeV(int P, int Q, int W) { // 500x tot
	V[P][Q]=W;
	compute_block(P/ML);
	compute_ans();
}

int escape(int V1, int V2) { // 200000x
	//return mat[0][V1][V2];
	return ans[cur][V1][V2];
}

컴파일 시 표준 에러 (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: 0 / 21
• Subtask 6: 0 / 24