Submission #28408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28408	2017-07-16T05:22:56 Z	tlwpdus 팬클럽 회장(#1123, kdh9949)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	0 / 1	33 ms	21640 KB

padak

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k, b, z, tr, *md[1010], cnt[1000010], ccnt[1000010], mn, mx, q[2000010], f, r;

int main(){
	scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
	if(n > m){ swap(n, m); tr = 1; }
	for(int i = 1; i <= n; i++){
		md[i] = new int[m + 1];
		fill(md[i] + 1, md[i] + m + 1, inf);
	}
	for(int x, y; k--; ){
		scanf("%d%d", &x, &y);
		if(tr) swap(x, y);
		md[x][y] = 0;
		q[r++] = x * 2 * m + y;
	}
	while(f < r){
		int x = q[f] / (2 * m), y = q[f] % (2 * m); f++;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if(md[nx][ny] > md[x][y] + 1){
				md[nx][ny] = md[x][y] + 1;
				q[r++] = nx * 2 * m + ny;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cnt[md[i][j]]++;
			ccnt[md[i][j]]++;
		}
	}
	for(int i = 1, j = 0; i <= n + m; i++){
		int t = z;
		j = max(j, i);
		while(t >= cnt[j]){
			mx += cnt[j];
			t -= cnt[j];
			cnt[j] = 0;
			j++;
			if(j > n + m) break;
		}
		if(j > n + m) break;
		if(t){
			mx += t;
			cnt[j] -= t;
		}
	}
	for(int i = 1, j = n + m; i <= n + m; i++){
		int t = z;
		while(t >= ccnt[j]){
			mn += ccnt[j];
			t -= ccnt[j];
			ccnt[j] = 0;
			j--;
			if(j < i) break;
		}
		if(j < i) break;
		if(t){
			mn += t;
			ccnt[j] -= t;
		}
	}
	printf("%d %d\n", mn, mx);
}

Compilation message

padak.cpp: In function 'int main()':
padak.cpp:8:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
                                         ^
padak.cpp:15:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	17652 KB	Output is correct
2	Correct	0 ms	17652 KB	Output is correct
3	Correct	33 ms	21612 KB	Output is correct
4	Correct	33 ms	21640 KB	Output is correct
5	Correct	29 ms	21592 KB	Output is correct
6	Incorrect	26 ms	21572 KB	Output isn't correct
7	Halted	0 ms	0 KB	-