Submission #501346

#	Time	Username	Problem	Language	Result	Execution time	Memory
501346		sidon	Mecho (IOI09_mecho)	C++17	100 / 100	177 ms	6136 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);
		}
	}
}
 
signed main(){
	cin >> N >> S;
 
 	for(int i = 0; i < N; i++)
 		cin >> _, g += _;

	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