Submission #28596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28596	2017-07-16T07:47:12 Z	욱제한테백구주나(#1214, sgc109, wookje, joonas)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	73 ms	65536 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;
vector<vector<int> > dist;
bool inRange(int i, int j){
	return 0 <= i && i < N && 0 <= j && j < M;
}
int cnt[2000003];
int backup[2000003];
int main() {
	cin >> N >> M >> K >> B >> Z;
	dist = vector<vector<int> >(N, vector<int>(M, -1));
	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[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[ni][nj] != -1) continue;
			dist[ni][nj] = dist[ci][cj] + 1;
			cnt[dist[ni][nj]]++;
			maxD = max(maxD, dist[ni][nj]);
			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	17648 KB	Output is correct
2	Correct	0 ms	17648 KB	Output is correct
3	Correct	36 ms	21608 KB	Output is correct
4	Correct	36 ms	21632 KB	Output is correct
5	Correct	29 ms	21592 KB	Output is correct
6	Correct	29 ms	24744 KB	Output is correct
7	Correct	33 ms	21632 KB	Output is correct
8	Correct	36 ms	25464 KB	Output is correct
9	Memory limit exceeded	73 ms	65536 KB	Memory limit exceeded
10	Halted	0 ms	0 KB	-