제출 #98072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98072		tincamatei	웜뱃 (IOI13_wombats)	C++14	12 / 100	75 ms	16128 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_C = 20;
const int MAX_R = 20;
const int INF = 1000000000;

int R, C;
int H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int sp[MAX_R][MAX_C];
int a[MAX_C][MAX_C];

struct Matrix {
	int dp[MAX_C][MAX_C];
	Matrix() {
		for(int i = 0; i < MAX_C; ++i)
			for(int j = 0; j < MAX_C; ++j)
				dp[i][j] = INF;
	}

	Matrix operator* (const Matrix &x) const {
		Matrix rez;
		for(int i = 0; i < C; ++i) {
			for(int j = 0; j < C; ++j) {
				int dist = dp[i][j] + x.dp[j][i];
				if(dist < rez.dp[i][i]) {
					rez.dp[i][i] = dist;
					a[i][i] = j;
				}
			}
		}

		for(int d = 1; d < C; ++d) {
			for(int i = 0; i < C - d; ++i) {
				int j = i + d;
				int st, dr;
				st = a[i][j - 1];
				dr = a[i + 1][j];
				for(int k = 0; k < C; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}

			for(int i = d; i < C; ++i) {
				int j = i - d;
				int st, dr;
				st = a[i - 1][j];
				dr = a[i][j + 1];
				for(int k = 0; k < C; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}
		}
		return rez;
	}
} dp[MAX_R];

Matrix rez;

void initrez() {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			if(i == j)
				rez.dp[i][j] = 0;
			else
				rez.dp[i][j] = INF;
}

void initrow(Matrix &x, int r) {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			x.dp[i][j] = abs(sp[r][i] - sp[r][j]) + V[r][j];
}

void calcrez() {
	initrez();
	for(int i = 0; i < R; ++i)
		rez = rez * dp[i];
}

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; ++j) {
			H[i][j] = _H[i][j];
			V[i][j] = _V[i][j];
		}

	for(int i = 0; i < R; ++i) {
		sp[i][0] = 0;
		for(int j = 1; j < C; ++j)
			sp[i][j] = sp[i][j - 1] + H[i][j - 1];
	}

	for(int i = 0; i < R; ++i)
		initrow(dp[i], i);

	calcrez();
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	for(int i = 1; i < C; ++i)
		sp[P][i] = sp[P][i - 1] + H[P][i - 1];
	initrow(dp[P], P);
	calcrez();
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	initrow(dp[P], P);
	calcrez();
}

int escape(int V1, int V2) {
	return rez.dp[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;
      ^~~
wombats.cpp: In member function 'Matrix Matrix::operator*(const Matrix&) const':
wombats.cpp:38:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
     int st, dr;
         ^~
wombats.cpp:38:13: warning: variable 'dr' set but not used [-Wunused-but-set-variable]
     int st, dr;
             ^~
wombats.cpp:52:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
     int st, dr;
         ^~
wombats.cpp:52:13: warning: variable 'dr' set but not used [-Wunused-but-set-variable]
     int st, dr;
             ^~

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