oj.uz

Submission #28704

# Submission time Handle Problem Language Result Execution time Memory
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 
#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

# Verdict Execution time Memory 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 -