제출 #123085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123085		MAMBA	웜뱃 (IOI13_wombats)	C++17	100 / 100	9264 ms	169816 KiB

wombats

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

using namespace std;

#define rep(i , j , k) for (int i = j ; i < (int)k; i++)

inline bool smin(int &l, int r) {
	if (r < l) return l = r, true;
	return false;
}

inline bool smax(int &l ,int r) {
	if (l < r) return l = r , true;
	return false;
}

const int LEN = 35;
const int MAXN = 5000 / LEN + 10;

int R , C;
int dist[MAXN][2][202][202];
int H[5000][200];
int V[5000][200];

struct segment {
	int d[202][202];	
	segment() {
		memset(d , 63 , sizeof(d));
	}
} seg[MAXN << 2];

void solve(int So , int Z, const segment &L, const segment &R , segment &res, int l , int r, int s , int t) {
	if (l >= r) return;
	int mid = l + r >> 1;

	int best = s;
	int val = 1e9 + 10;

	rep(i , s , t + 1)
		if (smin(val , L.d[So][i] +  V[Z][i] + R.d[i][mid]))
			best = i;
	res.d[So][mid] = val;
	solve(So , Z , L , R , res , l , mid , s , best);
	solve(So , Z , L , R , res , mid + 1 , r , best , t);
}

inline void merge(segment &res , const segment &l, const segment &r, int mid) {
	rep(so , 0 , C) 
		solve(so, mid * LEN - 1 , l , r , res, 0 , C, 0 , C - 1);
}


void build(int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
//	cout << "LETS BUILD : " << l << ' ' << r << endl;
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
			seg[id].d[i][j] = dist[l][0][i][j];
		return;
	}
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r ,id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);
}

void segUpt(int pos , int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
			seg[id].d[i][j] = dist[l][0][i][j];
		return;
	}
	int mid = l +r >> 1;
	if (pos < mid) segUpt(pos , l, mid , id << 1);
	else segUpt(pos , mid , r, id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);

}

inline void build_len(int id) {
	memset(dist[id] , 63 , sizeof(dist[id]));
	rep(i , 0 , C) {
		dist[id][0][i][i] = 0;
		rep(j , i + 1, C)
			dist[id][0][i][j] = dist[id][0][j][i] = dist[id][0][i][j - 1] + H[id * LEN][j - 1];
	}
	for (int i = id * LEN + 1; i < min(R , (id + 1) * LEN); i++) {
		memset(dist[id][1] , 63 , sizeof(dist[id][1]));
		rep(x , 0 , C) {
			for (int y = 0; y < C; y++) {
				smin(dist[id][1][x][y] , dist[id][0][x][y] + V[i - 1][y]);
				if (y)
					smin(dist[id][1][x][y] , dist[id][1][x][y - 1] + H[i][y - 1]);
			}
			for (int y = C - 1; ~y; y--) 
				if (y + 1 != C)
					smin(dist[id][1][x][y] , dist[id][1][x][y + 1] + H[i][y]);
		}
		/*
		rep(x , 0 , C)
			rep(y , 0 , C)
			cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
		cout << endl;
		*/
		rep(x , 0 , C) rep(y , 0 , C) dist[id][0][x][y] = dist[id][1][x][y];
	}
	/*
	rep(x , 0 , C)
		rep(y , 0 , C)
		cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
	*/
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
	R = R_ , C = C_;
	rep(i , 0 , R)
		rep(j , 0 , C - 1)
		H[i][j] = H_[i][j];
	rep(i , 0 , R - 1)
		rep(j , 0 , C)
		V[i][j] = V_[i][j];

	for (int i = 0; i * LEN  < R; i++)
		build_len(i);
	build();
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	build_len(P / LEN);
	segUpt(P / LEN);
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	build_len((P + 1) / LEN);
	segUpt(P / LEN);
}

int escape(int V1, int V2) {
	return seg[1].d[V1][V2];
}
/*
int main() {
	int r , c;
	cin >> r >> c;
	rep(i , 0 , r)
		rep(j , 0 , c - 1)
		cin >> H[i][j];
	rep(i , 0 , r - 1)
		rep(j , 0 , c)
		cin >> V[i][j];
	init(r , c , H , V);
	int e;
	cin >> e;
	while (e--) {
		int tp;
		cin >> tp;
		if (tp == 3) {
			int x , y;
			cin >> x >> y;
			cout << escape(x , y) << endl; 
		}
		else if (tp == 1) {
			int x , y , w;
			cin >> x >> y >> w;
			changeH(x ,y , w);
		}
		else {
			int x , y , w;
			cin >> x >> y >> w;
			changeV(x ,y , w);
		}
	}

	return 0;
}
*/

컴파일 시 표준 에러 (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 function 'void solve(int, int, const segment&, const segment&, segment&, int, int, int, int)':
wombats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void build(int, int, int)':
wombats.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void segUpt(int, int, int, int)':
wombats.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~

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