Submission #31450

#	Time	Username	Problem	Language	Result	Execution time	Memory
31450		jun6873	Wombats (IOI13_wombats)	C++11	28 / 100	20000 ms	28692 KiB

wombats

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

struct matrix {
	int a[202][202];
};

const int lim = 1;
int r, c, h[5004][204], v[5004][204], hs[5004][204], thr[204][204];
bool f[lim];
matrix m[lim], all;

void printmat(matrix k){
	for (int i=0; i<=c; i++) {
		for (int j=0; j<=c; j++) printf("%d ", k.a[i][j]);
		puts("");
	}
	puts("");
}

inline int hsum(int k, int x, int y) {
	if (x>y) swap(x, y);
	return x ? (hs[k][y] - hs[k][x]) : hs[k][y];
}

matrix sum(matrix &a, matrix &b, int k) {
	matrix ret;
	for (int i=0; i<=c; i++) thr[i][c-i+1] = c-1;
	for (int tog=0; tog<2; tog++) for (int j=c-1; j>=0; j--) for (int i=0; i+j<c; i++) {
		int mn = 2e9, mp = -1;
		int x = tog ? (i+j) : i, y = tog ? i : (i+j);
		for (int t=thr[j+1][i]; t<=thr[j+1][i+1]; t++) {
			int now = a.a[x][t] + v[k][t] + b.a[t][y];
			if (now <= mn) mn = now, mp = t;
		}
		if (tog) ret.a[i+j][i] = mn;
		else ret.a[i][i+j] = mn;
		thr[j][i+1] = mp;
	}
	return ret;
}

matrix base(int k) {
	matrix ret;
	for (int i=0; i<c; i++) for (int j=0; j<c; j++) ret.a[i][j] = hsum(k, i, j);
	return ret;
}

matrix get(int s, int e, int x, int all) {
	if (s==e) return base(s);
	if (!all and x<lim and f[x]) return m[x];
	int mid = (s+e)/2;
	if (x<lim) f[x] = 1;
	matrix l = get(s, mid, 2*x, all), r = get(mid+1, e, 2*x+1, all);
	matrix ret = sum(l, r, mid);
	if (x<lim) m[x] = ret;
	return ret;
}

matrix update(int s, int e, int x, int p) {
	if (s==e) return base(s);
	int k = (s+e)/2;
	if (p<=k) update(s, k, 2*x, p);
	else update(k+1, e, 2*x+1, p);
	if (x<lim) f[x] = 0;
	return get(s, e, x, 0);
}

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], hs[i][j+1] = hs[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];
    all = get(0, r-1, 1, 1);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    for (int j=0; j<c-1; j++) hs[P][j+1] = hs[P][j] + h[P][j];
    all = update(0, r-1, 1, P);
}

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

int escape(int V1, int V2) {
    return all.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]
  int res;
      ^

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