Submission #28654

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28654	2017-07-16T08:25:15 Z	욱제한테백구주나(#1214, sgc109, wookje, joonas)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	36 ms	65536 KB

padak

#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;

static char fast_buf[8192 * 32];
static int fast_len;
static int fast_idx;

int getInt() {
	int r, n;
	for (n = 0; ; fast_idx++) {
		if (fast_len == fast_idx) {
			int rd = fread(fast_buf, 1, sizeof(fast_buf), stdin);
			if (rd > 0) {
				fast_len = rd;
				fast_idx = 0;
			}
			else {
				return n;
			}
		}

		if (fast_buf[fast_idx] >= '0' && fast_buf[fast_idx] <= '9')
			n = n * 10 + (fast_buf[fast_idx] - '0');
		else if (n) {
			fast_idx++;
			return n;
		}
	}
}

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[1000003];
int main() {
	N = getInt();
	M = getInt();
	K = getInt();
	B = getInt();
	Z = getInt();

	for (int i = 0; i <= N; ++i) {
		dist[i] = new int[M + 10];
		fill(dist[i], dist[i] + M + 10, -1);
	}

	queue<pair<int, int> > q;
	for (int i = 0; i < K; i++) {
		int r = getInt();
		int c = getInt();
		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;
			int d = dist[ni][nj] = dist[ci][cj] + 1;
			cnt[d]++;
			maxD = max(maxD, d);
			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--;
		}
	}

	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++;
		}
	}

	printf("%d %d\n", ans1, ans2);
	return 0;
}

Compilation message

padak.cpp: In function 'int getInt()':
padak.cpp:22:6: warning: unused variable 'r' [-Wunused-variable]
  int r, n;
      ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	17900 KB	Output is correct
2	Correct	0 ms	17900 KB	Output is correct
3	Correct	36 ms	21860 KB	Output is correct
4	Correct	29 ms	21904 KB	Output is correct
5	Correct	29 ms	21848 KB	Output is correct
6	Correct	29 ms	27272 KB	Output is correct
7	Correct	26 ms	21884 KB	Output is correct
8	Correct	23 ms	25716 KB	Output is correct
9	Memory limit exceeded	36 ms	65536 KB	Memory limit exceeded
10	Halted	0 ms	0 KB	-