Submission #28633

# Submission time Handle Problem Language Result Execution time Memory
28633 2017-07-16T08:14:21 Z 욱제한테백구주나(#1214, sgc109, wookje, joonas) Oriental P.A.D.A.K (FXCUP2_padak) C++11
0 / 1
1000 ms 57252 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() {
	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 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 29 ms 13792 KB Output is correct
4 Correct 29 ms 13812 KB Output is correct
5 Correct 33 ms 13772 KB Output is correct
6 Correct 29 ms 15368 KB Output is correct
7 Correct 23 ms 13816 KB Output is correct
8 Correct 26 ms 13740 KB Output is correct
9 Correct 53 ms 48932 KB Output is correct
10 Correct 36 ms 13792 KB Output is correct
11 Correct 39 ms 13944 KB Output is correct
12 Correct 36 ms 13772 KB Output is correct
13 Correct 33 ms 15368 KB Output is correct
14 Correct 49 ms 13816 KB Output is correct
15 Correct 26 ms 13740 KB Output is correct
16 Correct 99 ms 48932 KB Output is correct
17 Correct 49 ms 14056 KB Output is correct
18 Correct 69 ms 14488 KB Output is correct
19 Correct 43 ms 14036 KB Output is correct
20 Correct 39 ms 15500 KB Output is correct
21 Correct 86 ms 14740 KB Output is correct
22 Correct 36 ms 13740 KB Output is correct
23 Correct 189 ms 48932 KB Output is correct
24 Correct 756 ms 22168 KB Output is correct
25 Correct 753 ms 22112 KB Output is correct
26 Correct 786 ms 22148 KB Output is correct
27 Correct 983 ms 23656 KB Output is correct
28 Correct 749 ms 22092 KB Output is correct
29 Correct 806 ms 21984 KB Output is correct
30 Execution timed out 1000 ms 57252 KB Execution timed out
31 Halted 0 ms 0 KB -