Submission #28618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28618	2017-07-16T08:03:56 Z	욱제한테백구주나(#1214, sgc109, wookje, joonas)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	1000 ms	57752 KB

padak

#include <bits/stdc++.h>
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() {
	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9840 KB	Output is correct
2	Correct	0 ms	9972 KB	Output is correct
3	Correct	309 ms	49612 KB	Output is correct
4	Correct	346 ms	49608 KB	Output is correct
5	Correct	353 ms	49608 KB	Output is correct
6	Correct	426 ms	49608 KB	Output is correct
7	Correct	346 ms	49608 KB	Output is correct
8	Correct	166 ms	49608 KB	Output is correct
9	Correct	429 ms	49608 KB	Output is correct
10	Correct	346 ms	49612 KB	Output is correct
11	Correct	646 ms	49628 KB	Output is correct
12	Correct	516 ms	49616 KB	Output is correct
13	Correct	536 ms	49620 KB	Output is correct
14	Correct	386 ms	49616 KB	Output is correct
15	Correct	339 ms	49608 KB	Output is correct
16	Correct	553 ms	49608 KB	Output is correct
17	Correct	593 ms	49652 KB	Output is correct
18	Correct	866 ms	49664 KB	Output is correct
19	Correct	839 ms	49652 KB	Output is correct
20	Correct	783 ms	49652 KB	Output is correct
21	Correct	739 ms	49668 KB	Output is correct
22	Correct	426 ms	49624 KB	Output is correct
23	Correct	739 ms	49652 KB	Output is correct
24	Execution timed out	1000 ms	57752 KB	Execution timed out
25	Halted	0 ms	0 KB	-