Submission #1067956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067956		sleepntsheep	Wombats (IOI13_wombats)	C++17	27 / 100	38 ms	13148 KiB

wombats

#pragma GCC optimize("O3,unroll-loops")
#include "wombats.h"
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

#ifndef ROW
#define ROW 5000
#endif

int r, c, h[ROW][100], v[ROW + 1][100];

struct node {
	int a[2][2] {};
	node() {}
	node(int row) {
		static int ph[100];
		ph[0] = 0;
		for (int j = 0; j + 1 < c; ++j)
			ph[j + 1] = ph[j] + h[row][j];

		for (int i = 0; i < c; ++i) {
			for (int j = 0; j < c; ++j)
				if (j < i)
					a[i][j] = v[row][j] + ph[i] - ph[j];
				else
					a[i][j] = v[row][j] + ph[j] - ph[i];
		}
	}
	
	node (node up, node down) {
		for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) {
			a[i][j] = 1e9;
			for (int k = 0; k < c; ++k)
				a[i][j] = min(a[i][j], up.a[i][k] + down.a[k][j]);
		}
	}
};

node st[20001];

void build(int v, int l, int r) {
	if (l == r) {
		st[v] = node(l);
		return;
	}
	int m  = (l + r) / 2;
	build(2 * v + 1, l, m);
	build(2 * v + 2, m + 1, r);
	st[v] = node(st[v * 2 + 1], st[v * 2 + 2]);
}

void upd(int v, int l, int r, int k) {
	if (l == r) {
		st[v] = node(l);
		return;
	}
	int m  = (l + r) / 2;
	if (k <= m) upd(2 * v + 1, l, m, k);
	else upd(2 * v + 2, m + 1, r, k);
	st[v] = node(st[v * 2 + 1], st[v * 2 + 2]);
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	upd(0, 0, r - 1, P);
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	upd(0, 0, r - 1, P);
}

void init(int R, int C, int H[ROW][200], int V[ROW][200]) {
	r = R, c = C;
	for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j)
		v[i][j] = V[i][j];
	for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j)
		h[i][j] = H[i][j];
	build(0, 0, r - 1);
}

int escape(int V1, int V2) {
	auto &x = st[0];
	return x.a[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;
      |      ^~~

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