제출 #780980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780980		NothingXD	웜뱃 (IOI13_wombats)	C++17	12 / 100	116 ms	32916 KiB

wombats

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e3 + 10;
const int maxm = 200 + 10;
const int sq = 1;
const int inf = 1e9;
int n, m, h[maxn][maxm], v[maxn][maxm], dp[maxn][maxm], val[50][maxm][maxm], seg[210][maxm][maxm], ptrdp[maxm][maxm];

void change(int v, int l, int r, int idx){
	if (l + 1 == r){
		//debug(v, l, r);
		for (int i = 0; i < m; i++){
			for (int j = 0; j < m; j++){
				seg[v][i][j] = val[l][i][j];
		//		debug(i, j, seg[v][i][j]);
			}
		}
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid){
		change(v << 1, l, mid, idx);
	}
	else{
		change(v << 1 | 1, mid, r, idx);
	}
	//debug(v, l, r);
	int ptr = mid * sq - 1;
	for (int shib = m-1; shib >= 1-m; shib--){
		for (int i = 0; i < m; i++){
			int j = i - shib;
			if (j < 0 || j >= m) continue;
			int l = (j? ptrdp[i][j-1]: 0);
			int r = (i+1 < m? ptrdp[i+1][j]: m-1);
			//debug(i, j, l, r);
			ptrdp[i][j] = l;
			seg[v][i][j] = seg[v << 1][i][l] + seg[v << 1 | 1][l][j] + ::v[ptr][l];
			for (int k = l+1; k <= r; k++){
				int tmp = seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[ptr][k];
				if (tmp < seg[v][i][j]){
					seg[v][i][j] = tmp;
					ptrdp[i][j] = k;
				}
			}
			//debug(seg[v][i][j], ptrdp[i][j]);
		}
	}
}

inline void update(int r){
	for (int i = 1; i < m; i++){
		dp[r][i] = min(dp[r][i], dp[r][i-1] + h[r][i-1]);
	}
	for (int i = m-2; ~i; i--){
		dp[r][i] = min(dp[r][i], dp[r][i+1] + h[r][i]);
	}
}

inline void build(int blc){
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			if (i == j) dp[blc*sq][j] = 0;
			else dp[blc*sq][j] = inf;
		}
		update(blc*sq);
		int idx = min((blc+1)*sq, n) - 1;
		for (int j = blc*sq+1; j <= idx; j++){
			for (int k = 0; k < m; k++){
				dp[j][k] = dp[j-1][k] + v[j-1][k];
			}
			update(j);
		}
		for (int j = 0; j < m; j++){
			val[blc][i][j] = dp[idx][j];
		}
	}
	change(1, 0, (n-1)/sq+1, blc);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R, m = C;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m-1; j++){
			h[i][j] = H[i][j];
		}
	}
	for (int i = 0; i < n-1; i++){
		for (int j = 0; j < m; j++){
			v[i][j] = V[i][j];
		}
	}
	for (int i = 0; i <= (n-1)/sq; i++){
		build(i);
	}
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	build(P/sq);
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	build(P/sq);
}

int escape(int V1, int V2) {
	return seg[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: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24