제출 #60263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60263		ksun48	웜뱃 (IOI13_wombats)	C++14	76 / 100	20026 ms	263168 KiB

wombats

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

typedef vector<vector<int> > Paths;
const int MAXD = 100000000; // 1e8

int r;
int c;

vector<vector<int> > h;
vector<vector<int> > v;

void pr(const Paths &ans){
	for(int i = 0; i < c; i++){
		for(int j = 0; j < c; j++){
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void dnc(const Paths &a, const Paths &b, Paths &paths, int t, int bl, int br, int ml, int mr){
	if(bl > br) return;
	// top, bottom left, bottom right
	int bm = (bl + br) / 2;
	int best = MAXD + 1;
	int bestm = -1;
	for(int m = ml; m <= mr; m++){
		int dist = a[t][m] + b[m][bm];
		if(dist < best){
			best = dist;
			bestm = m;
		}
	}
	assert(bestm != -1);
	paths[t][bm] = best;
	dnc(a, b, paths, t, bl, bm - 1, ml, bestm);
	dnc(a, b, paths, t, bm + 1, br, bestm, mr);
}

Paths join(const Paths &a, const Paths &b){
	Paths paths(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		dnc(a, b, paths, i, 0, c-1, 0, c-1);
	}
	return paths;
}

Paths horizontal(int row){
	vector<int> psums(c);
	psums[0] = 0;
	for(int i = 1; i < c; i++){
		psums[i] = psums[i-1] + h[row][i-1];
	}
	Paths paths(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		for(int j = 0; j < c; j++){
			paths[i][j] = abs(psums[j] - psums[i]);
		}
	}
	return paths;
}

Paths empty(){
	Paths p2(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		p2[i][i] = 0;
	}
	return p2;
}

Paths make(int row){
	Paths p2(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		p2[i][i] = v[row][i];
	}
	return join(horizontal(row), join(p2, horizontal(row + 1)));
}

Paths make_interval(int r1, int r2){
	Paths p = empty();
	for(int a = r1; a <= r2; a++){
		p = join(p, make(a));
	}
	return p;
}

Paths ans;

struct node {
	Paths p;
	node *l, *r;
	int lx, rx;
};

const int BLOCKSZ = 7;

node* build(int lx, int rx){
	node* v = new node();
	v->lx = lx;
	v->rx = rx;
	if(rx - lx + 1 <= BLOCKSZ){
		v->l = v->r = NULL;
		v->p = make_interval(v->lx, v->rx);
	} else {
		int mx = (lx + rx) / 2;
		v->l = build(lx, mx);
		v->r = build(mx + 1, rx);
		v->p = join(v->l->p, v->r->p);
	}
	return v;
}

void upd(node* v, int x){
	if(x < v->lx || x > v->rx) return;
	if(v->l == NULL && v->r == NULL){
		v->p = make_interval(v->lx, v->rx);
	} else {
		upd(v->l, x);
		upd(v->r, x);
		v->p = join(v->l->p, v->r->p);
	}
}

node* tree;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R;
	c = C;
	h.resize(r, vector<int>(c-1, 0));
	v.resize(r-1, vector<int>(c, 0));
	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];
		}
	}
	tree = build(0, r-2);
}

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

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	upd(tree, P);
}

int escape(int V1, int V2) {
	return tree->p[V1][V2];
}

컴파일 시 표준 에러 (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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24