제출 #1252348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252348		gs13105	웜뱃 (IOI13_wombats)	C++20	76 / 100	20085 ms	20020 KiB

wombats

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#include "wombats.h"

const int INF = 1e9;
const int Bcnt = 21;
const int B = (5000 + Bcnt - 1) / Bcnt;
int R, C;
int H[5000][200];
int V[5000][200];

int mem[Bcnt][200][200];
int dp1[200];
void upd(int b)
{
	int s = b * B;
	int l = min(B, R - s);
	for(int i = 0; i < C; i++)
	{
		for(int j = 0; j < C; j++)
			dp1[j] = INF;
		dp1[i] = 0;
		for(int j = 0; j < l; j++)
		{
			for(int k = 1; k < C; k++)
				dp1[k] = min(dp1[k], dp1[k - 1] + H[j + s][k - 1]);
			for(int k = C - 2; k >= 0; k--)
				dp1[k] = min(dp1[k], dp1[k + 1] + H[j + s][k]);
			for(int k = 0; k < C; k++)
				dp1[k] += V[j + s][k];
		}
		for(int j = 0; j < C; j++)
			mem[b][i][j] = dp1[j];
	}
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
	R = _R;
	C = _C;
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C - 1; j++)
			H[i][j] = _H[i][j];
	for(int i = 0; i < R - 1; i++)
		for(int j = 0; j < C; j++)
			V[i][j] = _V[i][j];

	for(int i = 0; i < (R + B - 1) / B; i++)
		upd(i);
}

int sav[200];
int snum = 1;

void changeH(int P, int Q, int W)
{
	snum++;
	H[P][Q] = W;
	upd(P / B);
}

void changeV(int P, int Q, int W)
{
	snum++;
	V[P][Q] = W;
	upd(P / B);
}

int dp2[Bcnt][200];
int fb;
void f(int l, int r, int s, int g)
{
	if(r <= l)
	{
		if(l == r)
		{
			int v = INF;
			for(int i = s; i <= g; i++)
				v = min(v, dp2[fb - 1][i] + mem[fb][i][l]);
			dp2[fb][l] = v;
		}
		return;
	}

	int x = (l + r) / 2, v = INF, p;
	for(int i = s; i <= g; i++)
	{
		int t = dp2[fb - 1][i] + mem[fb][i][x];
		if(t < v)
		{
			v = t;
			p = i;
		}
	}
	dp2[fb][x] = v;
	f(l, x - 1, s, p);
	f(x + 1, r, p, g);
}

int ans[200][200];
int escape(int V1, int V2)
{
	if(sav[V1] != snum)
	{
		sav[V1] = snum;
		for(int i = 0; i < C; i++)
			dp2[0][i] = mem[0][V1][i];
		for(int i = 1; i < (R + B - 1) / B; i++)
		{
			fb = i;
			f(0, C - 1, 0, C - 1);
		}
		for(int i = 0; i < C; i++)
			ans[V1][i] = dp2[(R - 1) / B][i];
	}
	return ans[V1][V2];
}

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