Submission #28448

#	Time	Username	Problem	Language	Result	Execution time	Memory
28448		슈퍼스타 tlwpdus (#68)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	0 ms	6908 KiB

padak

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int n, m, k, b, z;
bool visit[1000100];
int cnt[1000100];

int px[] = {1,0,-1,0}, py[] = {0,1,0,-1};

bool ok(int x, int y) {
	return x>=0&&x<n&&y>=0&&y<m;
}

int main() {
	int i;

	scanf("%d%d%d%d%d",&n,&m,&k,&b,&z);
	queue<pii> qu;
	for (i=0;i<k;i++) {
		int a, b;
		scanf("%d%d",&a,&b); --a; --b;
		qu.push(pii(0,a*m+b)); visit[a*m+b] = 1;
	}
	int md = 0;
	while(!qu.empty()) {
		pii tmp = qu.front(); qu.pop();
		int here = tmp.second, d = tmp.first;
		cnt[d]++; md = d;
		int x = here/m, y = here%m;
		for (i=0;i<4;i++) {
			int nx = x+px[i], ny = y+py[i];
			if (!ok(nx,ny)||visit[nx*m+ny]) continue;
			qu.push(pii(d+1,nx*m+ny)); visit[nx*m+ny] = 1;
		}
	}
	int maxi = 0; int p = 0, q = 1;
	for (i=0;i<=md;i++) {
		q = max(q,i+1);
		int rem = z;
		while(q<=md&&rem) {
			int v = min(rem,cnt[q]);
			rem -= v;
			cnt[q] -= v;
			maxi += v;
			q++;
		}
		rem = b;
		while(p<=i&&rem) {
			int v = min(rem,cnt[p]);
			rem -= v;
			cnt[p] -= v;
			p++;
		}
	}
	int mini = 0; p = 0, q = md;
	set<int> s;
	for (i=0;i<=md;i++) s.insert(i);
	for (i=0;i<=md;i++) {
		p = i;
		int rem = b;
		while(rem) {
			int v = min(rem,cnt[p]);
			cnt[p] -= v;
			rem -= v;
			if (cnt[p]==0) {
				s.erase(p);
			}
			else break;
			auto it = s.lower_bound(p);
			if (it==s.begin()) break;
			p = *(--it);
		}
		q = md;
		rem = z;
		while(q>i&&rem) {
			int v = min(rem,cnt[q]);
			cnt[q] -= v;
			rem -= v;
			mini += v;
			if (cnt[q]==0) {
				s.erase(q);
			}
			else break;
			auto it = s.lower_bound(q);
			if (it==s.begin()) break;
			q = *(--it);
		}
	}
	printf("%d %d\n",mini,maxi);

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 1