Submission #28714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28714	2017-07-16T08:59:30 Z	맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	0 / 1	643 ms	65536 KB

padak

#include<stdio.h>
#include<vector>
#include<queue>

using lint = long long int;
using pii = std::pair<int, int>;

using std::vector;
using std::queue;

int xx[4] = { 0, 0, 1, -1 };
int yy[4] = { 1, -1, 0, 0 };
vector< vector<int>> graph;
int cou[2001000];
queue<pii> qu;

int main(void) {
	int N, M, K, B, Z;
	scanf("%d %d %d %d %d", &N, &M, &K, &B, &Z);
	
	if ((lint)N * M > 1000000) {
		return 0;
	}

	graph.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		graph[i].resize(M + 1, 10010000);
	}

	for (int i = 1; i <= K; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		graph[t1][t2] = 0;
		qu.push(pii(t1, t2));
	}

	int val = 1;
	while (!qu.empty()) {
		int cou = qu.size();
		for(int asdf = 1; asdf <= cou; asdf++){
			int x = qu.front().first;
			int y = qu.front().second;
			qu.pop();

			for (int i = 0; i < 4; i++) {
				if (0 < x + xx[i] && x + xx[i] <= N && 0 < y + yy[i] && y + yy[i] <= M) {
					if (graph[x + xx[i]][y + yy[i]] > val) {
						graph[x + xx[i]][y + yy[i]] = val;
						qu.push(pii(x + xx[i], y + yy[i]));
					}
				}
			}
		}
		val++;
	}

	int maxi = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			maxi = std::max(maxi, graph[i][j]);
			cou[graph[i][j]]++;
		}
	}

	int ans1 = 0, ans2 = 0;
	int rest = 0;
	for (int i = 1; i <= maxi; i++) {
		if (Z <= cou[i]) {
			ans1 += Z;
			if (cou[i] - Z >= rest) {
				ans1 += rest;
				rest = 0;
			}
			else {
				ans1 += cou[i] - Z;
				rest -= cou[i] - Z;
			}
		}
		else {
			ans1 += cou[i];
			rest += Z - cou[i];
		}
	}
	int ind = maxi;
	for (int i = 1; i <= maxi; i++) {
		if (i > ind) {
			break;
		}
		int cur = 0;
		while (cur < Z) {
			if (cou[ind] >= Z - cur) {
				cou[ind] -= Z - cur;
				cur = Z;
			}
			else {
				cur += cou[ind];
				ind--;
			}
			if (i > ind) {
				break;
			}
		}
		ans2 += cur;
		if (i > ind) {
			break;
		}
	}

	printf("%d %d", ans2, ans1);

	return 0;
}

Compilation message

padak.cpp: In function 'int main()':
padak.cpp:19:45: 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:32:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
                           ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9752 KB	Output is correct
2	Correct	0 ms	9752 KB	Output is correct
3	Correct	29 ms	13712 KB	Output is correct
4	Correct	29 ms	13736 KB	Output is correct
5	Correct	26 ms	13696 KB	Output is correct
6	Correct	29 ms	18300 KB	Output is correct
7	Correct	33 ms	13736 KB	Output is correct
8	Correct	26 ms	13660 KB	Output is correct
9	Correct	126 ms	64476 KB	Output is correct
10	Correct	33 ms	13712 KB	Output is correct
11	Correct	43 ms	13868 KB	Output is correct
12	Correct	33 ms	13696 KB	Output is correct
13	Correct	63 ms	18432 KB	Output is correct
14	Correct	29 ms	13736 KB	Output is correct
15	Correct	23 ms	13660 KB	Output is correct
16	Correct	146 ms	64476 KB	Output is correct
17	Correct	46 ms	13976 KB	Output is correct
18	Correct	103 ms	14396 KB	Output is correct
19	Correct	59 ms	13960 KB	Output is correct
20	Correct	46 ms	18564 KB	Output is correct
21	Correct	69 ms	14660 KB	Output is correct
22	Correct	29 ms	13660 KB	Output is correct
23	Correct	249 ms	64476 KB	Output is correct
24	Correct	433 ms	22092 KB	Output is correct
25	Correct	466 ms	22044 KB	Output is correct
26	Correct	459 ms	22072 KB	Output is correct
27	Correct	643 ms	26700 KB	Output is correct
28	Correct	446 ms	22016 KB	Output is correct
29	Correct	399 ms	21904 KB	Output is correct
30	Memory limit exceeded	146 ms	65536 KB	Memory limit exceeded
31	Halted	0 ms	0 KB	-