제출 #433541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433541		nvmdava	웜뱃 (IOI13_wombats)	C++17	100 / 100	5714 ms	184968 KiB

wombats

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

const int SZ = 10;
int h[5001][201], v[5001][201];
int st[1024][201][201];
int r, c;

int opt[201];

void update(int id, int le, int ri, int L, int R){
	if(ri < L || le > R) return;
	if(le == ri){
		memset(st[id], 0x3f, sizeof st[id]);
		for(int i = 0; i < c; ++i){
			st[id][i][i] = 0;
			for(int k = le * SZ; k < min((le + 1) * SZ, r); ++k){
				for(int j = 1; j < c; ++j)
					st[id][i][j] = min(st[id][i][j], st[id][i][j - 1] + h[k][j - 1]);
				for(int j = c - 2; j >= 0; --j)
					st[id][i][j] = min(st[id][i][j], st[id][i][j + 1] + h[k][j]);
				for(int j = 0; j < c; ++j)
					st[id][i][j] += v[k][j];
			}
		}
		return;
	}
	int m = (le + ri) >> 1;
	update(id << 1, le, m, L, R);
	update(id << 1 | 1, m + 1, ri, L, R);
	memset(opt, 0, sizeof opt);
	opt[c] = c - 1;

	for(int i = 0; i < c; ++i){
		for(int j = c - 1; j >= 0; --j){
			pair<int, int> mn = {INT_MAX, 0};
			for(int k = opt[j]; k <= opt[j + 1]; ++k)
				mn = min(mn, {st[id << 1][i][k] + st[id << 1 | 1][k][j], -k});
			opt[j] = -mn.second;
			st[id][i][j] = mn.first;
		}
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R; c = C;

    for(int i = 0; i < R - 1; ++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 < C - 1; ++j)
    		h[i][j] = H[i][j];

    update(1, 0, (r - 1) / SZ, 0, (r - 1) / SZ);
}

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

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

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

컴파일 시 표준 에러 (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