제출 #501344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501344		sidon	Mecho (IOI09_mecho)	C++17	100 / 100	176 ms	6084 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
 
const int Z = 1<<20;
const int dx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
int N, S, h[Z], m[Z], ans = -1, e, r;
string g, _;
 
void BFS(char src, int *d) {
	fill(d, d + N * N, Z);
	queue<int> q;
	for(int i = N * N; --i >= 0; ) {
		if(g[i] == src && ans < h[i])
			d[i] = 0, q.push(i);
		if(g[i] == 'D') e = i, g[i] = 30;
	}
 
	while(!empty(q)) {
		int k = q.front(), i = k / N, j = k % N; q.pop();

		for(auto &[s, t] : dx) {
			int x = i + s, y = j + t, z = x * N + y;
 
			if(min(x, y) < 0 || max(x, y) >= N || d[z] != Z) continue;
			if((g[z] & 1 || g[z] == r) && (!r || (d[k] + 1) / S + ans < h[z]))
				d[z] = d[k] + 1, q.push(z);
		}
	}
}

#define gc getchar_unlocked()

void ri(int &I){
	char J = I = 0;
	for(; J < 48; J=gc);
	for(; J > 47; J=gc) I = I * 10 + J - 48;
}
 
signed main(){
	ri(N), ri(S);
 
 	for(int i = 0; i < N; i++, gc)
 		for(int j = 0; j < N; j++)
			g += gc;

	BFS('H', h);

	for(int b = r = 30; --b >= 0; ) {
		ans += 1 << b;
		BFS('M', m);
		if(m[e] == Z)	ans -= 1 << b;
	}

	cout << ans;
}

• Subtask 1: 100 / 100