답안 #28663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28663	2017-07-16T08:29:45 Z	욱제한테백구주나(#1214, sgc109, wookje, joonas)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	1000 ms	57868 KB

padak

#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;

int N, M, K, B, Z;
unordered_map<ll, int> dist;
bool inRange(int i, int j){
	return 0 <= i && i < N && 0 <= j && j < M;
}
int cnt[1000003];
int backup[1000003];
int main() {
	fastio();
	cin >> N >> M >> K >> B >> Z;
	queue<pair<int,int> > q;
	for(int i = 0 ; i < K; i++){
		int r,c;
		cin >> r >> c;
		r--, c--;
		q.push({r, c});
		dist[1000000 * r + c] = 0;
	}
	int maxD = 0;
	while(!q.empty()){
		auto p = q.front();
		q.pop();
		int ci = p.first;
		int cj = p.second;
		for(int k = 0 ; k < 4; k++){
			int ni = ci + "1021"[k] - '1';
			int nj = cj + "0112"[k] - '1';
			if(!inRange(ni, nj) || dist.find(1000000 * ni + nj) != dist.end()) continue;
			int d = dist[1000000 * ni + nj] = dist[1000000 * ci + cj] + 1;
			cnt[d]++;
			maxD = max(maxD, d);
			q.push({ni, nj});
		}
	}
	for(int i = 0; i <= maxD; i++) backup[i] = cnt[i];
	int ans1 = 0;
	int t = 0;
	int cur = Z;
	for(int i = maxD; t < i;) {
		if(cnt[i] > cur){
			cnt[i] -= cur;
			ans1 += cur;
			cur = Z;
			t++;
		}
		else {
			cur -= cnt[i];
			ans1 += cnt[i];
			i--;
		}
	}
	cout << ans1 << endl;

	for(int i = 0 ; i <= maxD; i++) cnt[i] = backup[i];

	int ans2 = 0;
	t = 0;
	int pos = 1;
	cur = Z;
	while(t < maxD && pos <= maxD) {
		if(t == pos) pos = t + 1;
		if(cnt[pos] > cur){
			cnt[pos] -= cur;
			ans2 += cur;
			cur = Z;
			t++;
		}
		else {
			cur -= cnt[pos];
			ans2 += cnt[pos];
			pos++;
		}
	}

	cout << ans2;
	return 0;
}

Subtask #1

0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	10000 KB	Output is correct
2	Correct	0 ms	10132 KB	Output is correct
3	Correct	286 ms	49728 KB	Output is correct
4	Correct	293 ms	49724 KB	Output is correct
5	Correct	339 ms	49724 KB	Output is correct
6	Correct	406 ms	49724 KB	Output is correct
7	Correct	309 ms	49724 KB	Output is correct
8	Correct	156 ms	49724 KB	Output is correct
9	Correct	359 ms	49724 KB	Output is correct
10	Correct	349 ms	49728 KB	Output is correct
11	Correct	519 ms	49744 KB	Output is correct
12	Correct	596 ms	49736 KB	Output is correct
13	Correct	536 ms	49736 KB	Output is correct
14	Correct	413 ms	49732 KB	Output is correct
15	Correct	366 ms	49724 KB	Output is correct
16	Correct	543 ms	49724 KB	Output is correct
17	Correct	526 ms	49768 KB	Output is correct
18	Correct	696 ms	49780 KB	Output is correct
19	Correct	776 ms	49768 KB	Output is correct
20	Correct	703 ms	49768 KB	Output is correct
21	Correct	729 ms	49784 KB	Output is correct
22	Correct	393 ms	49740 KB	Output is correct
23	Correct	736 ms	49768 KB	Output is correct
24	Execution timed out	1000 ms	57868 KB	Execution timed out
25	Halted	0 ms	0 KB	-