Submission #28772

# Submission time Handle Problem Language Result Execution time Memory
28772 2017-07-17T07:29:36 Z sgc109 Oriental P.A.D.A.K (FXCUP2_padak) C++11
1 / 1
743 ms 57368 KB
#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;
bool inRange(int i, int j){
	return 0 <= i && i < N && 0 <= j && j < M;
}
int cnt[1000003];
int backup[1000003];	
int** dist;
queue<pair<int,int> > q;
int main() {
	ios_base::sync_with_stdio(false),cin.tie(0);
	cin >> N >> M >> K >> B >> Z;
	dist = (int**)malloc(sizeof(int*) * N);
	for(int i = 0 ; i < N; i++) dist[i] = (int*)malloc(sizeof(int) * M);
	for(int i = 0 ; i < N; i++) for(int j = 0 ; j < M; j++) dist[i][j] = -1;
	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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 9992 KB Output is correct
2 Correct 0 ms 9992 KB Output is correct
3 Correct 29 ms 13952 KB Output is correct
4 Correct 36 ms 13844 KB Output is correct
5 Correct 36 ms 13936 KB Output is correct
6 Correct 26 ms 15396 KB Output is correct
7 Correct 26 ms 13932 KB Output is correct
8 Correct 23 ms 13900 KB Output is correct
9 Correct 66 ms 49092 KB Output is correct
10 Correct 36 ms 13952 KB Output is correct
11 Correct 53 ms 13976 KB Output is correct
12 Correct 29 ms 13936 KB Output is correct
13 Correct 33 ms 15396 KB Output is correct
14 Correct 19 ms 13932 KB Output is correct
15 Correct 33 ms 13900 KB Output is correct
16 Correct 113 ms 49092 KB Output is correct
17 Correct 39 ms 14216 KB Output is correct
18 Correct 49 ms 14636 KB Output is correct
19 Correct 39 ms 14200 KB Output is correct
20 Correct 33 ms 15528 KB Output is correct
21 Correct 66 ms 14856 KB Output is correct
22 Correct 33 ms 13900 KB Output is correct
23 Correct 183 ms 49092 KB Output is correct
24 Correct 326 ms 22232 KB Output is correct
25 Correct 333 ms 22228 KB Output is correct
26 Correct 326 ms 22216 KB Output is correct
27 Correct 446 ms 23772 KB Output is correct
28 Correct 343 ms 22208 KB Output is correct
29 Correct 356 ms 22080 KB Output is correct
30 Correct 743 ms 57368 KB Output is correct
31 Correct 39 ms 13952 KB Output is correct
32 Correct 66 ms 49092 KB Output is correct