답안 #28704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28704	2017-07-16T08:54:11 Z	맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	0 / 1	36 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[1001000];
int aaaaa[4][1001000];
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:20: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:33: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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	21484 KB	Output is correct
2	Correct	0 ms	21484 KB	Output is correct
3	Correct	36 ms	25444 KB	Output is correct
4	Correct	29 ms	25468 KB	Output is correct
5	Correct	29 ms	25428 KB	Output is correct
6	Correct	26 ms	30032 KB	Output is correct
7	Correct	29 ms	25468 KB	Output is correct
8	Correct	26 ms	25392 KB	Output is correct
9	Memory limit exceeded	19 ms	65536 KB	Memory limit exceeded
10	Halted	0 ms	0 KB	-