Submission #437509

#	Time	Username	Problem	Language	Result	Execution time	Memory
437509		cmwqfcmwqf	Wombats (IOI13_wombats)	C++14	100 / 100	3874 ms	183844 KiB

wombats

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

#define ls node << 1
#define rs node << 1 | 1

const int BK = 10, INF = 1.5e9;

int n, m, lim;
int A[5005][205], B[5005][205];
int f[10][205][205], sum[205], p[205][205];
int T[1025][205][205];

void get(int node, int id)
{
	int l = (id - 1) * BK + 1, r = min(n, id * BK), now = 0;
	for(int i = 1; i <= m; i++)
	{
		for(int j = i + 1; j <= m; j++)
			f[now][i][j] = f[now][i][j - 1] + A[l][j - 1];
		for(int j = i - 1; j >= 1; j--)
			f[now][i][j] = f[now][i][j + 1] + A[l][j];
	}
	for(int k = l + 1; k <= r; k++)
	{
		now ++;
		for(int i = 1; i < m; i++) sum[i] = sum[i - 1] + A[k][i];
		for(int i = 1; i <= m; i++)
		{
			int mn = INF;
			for(int j = 1; j <= m; j++)
			{
				mn = min(mn, f[now - 1][i][j] + B[k - 1][j] - sum[j - 1]);
				f[now][i][j] = mn + sum[j - 1];
			}
			mn = INF;
			for(int j = m; j >= 1; j--)
			{
				mn = min(mn, f[now - 1][i][j] + B[k - 1][j] + sum[j - 1]);
				f[now][i][j] = min(f[now][i][j], mn - sum[j - 1]);
			}
		}
	}
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= m; j++)
			T[node][i][j] = f[now][i][j];
}

void pushup(int node, int mid)
{
	mid *= BK;
	for(int l = m; l >= 1; l--)
		for(int r = 1; r <= m; r++)
		{
			int nl = (r == 1 ? 1 : p[l][r - 1]), nr = (l == m ? m : p[l + 1][r]);
			T[node][l][r] = INF;
			for(int md = nl; md <= nr; md++)
			{
				int tp = T[ls][l][md] + B[mid][md] + T[rs][md][r];
				if(tp < T[node][l][r]) T[node][l][r] = tp, p[l][r] = md;
			}
		}
}

void build(int node, int l, int r)
{
	if(l == r)
	{
		get(node, l);
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(node, mid);
}

void change(int node, int l, int r, int x)
{
	if(l == r)
	{
		get(node, l);
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) change(ls, l, mid, x);
	else change(rs, mid + 1, r, x);
	pushup(node, mid);
}

void changeH(int P, int Q, int W)
{
	P ++, Q ++;
	A[P][Q] = W;
	change(1, 1, lim, (P - 1) / BK + 1);
}

void changeV(int P, int Q, int W)
{
	P ++, Q ++;
	B[P][Q] = W;
	change(1, 1, lim, (P - 1) / BK + 1);
}

int escape(int V1, int V2)
{
	V1 ++, V2 ++;
	return T[1][V1][V2];
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
	n = R, m = C;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < m; j++)
			A[i][j] = H[i - 1][j - 1];
	for(int i = 1; i < n; i++)
		for(int j = 1; j <= m; j++)
			B[i][j] = V[i - 1][j - 1];
	lim = (n - 1) / BK + 1;
	build(1, 1, lim);
}

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