Submission #28564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28564	2017-07-16T07:25:54 Z	ㅁㄴㅇㄹ(#1150, TAMREF, Diuven, suhgyuho_william)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	1 / 1	806 ms	52840 KB

padak

#include <bits/stdc++.h>
#include <unistd.h>

#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define lld long long
#define Inf 1000000000
#define get gett

using namespace std;

int N,M,K,B,Z;
int ans1,ans2;
int **a;
int *tmp;
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
int qx[1000002],qy[1000002],rear,top;

int main(){
	scanf("%d %d %d %d %d",&N,&M,&K,&B,&Z);
	a = (int**)malloc(sizeof(int*)*(N+2));
	for(int i=0; i<=N+1; i++){
		a[i] = (int*)malloc(sizeof(int)*(M+2));
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) a[i][j] = Inf;
	for(int i=1; i<=K; i++){
		int x,y;
		scanf("%d %d",&x,&y);
		rear++;
		qx[rear] = x; qy[rear] = y;
		a[x][y] = 0;
	}
	while(top < rear){
		int x,y;
		top++;
		x = qx[top];
		y = qy[top];
		for(int i=0; i<4; i++){
			if(x+dx[i] < 1 || x+dx[i] > N || y+dy[i] < 1 || y+dy[i] > M) continue;
			if(a[x+dx[i]][y+dy[i]] <= a[x][y]+1) continue;
			a[x+dx[i]][y+dy[i]] = a[x][y]+1;
			rear++;
			qx[rear] = x+dx[i];
			qy[rear] = y+dy[i];
		}
	}
	tmp = (int*)malloc(sizeof(int)*(N*M+1));
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) tmp[(i-1)*M+j] = a[i][j];
	sort(tmp+1,tmp+N*M+1);
	int it,cnt;
	cnt = 0; it = 1;
	while(it <= N*M){
		while(it <= N*M && tmp[it] <= cnt) it++;
		for(int i=1; i<=Z && it <= N*M; i++){
			it++;
			ans2++;
		}
		cnt++;
	}
	reverse(tmp+1,tmp+N*M+1);
	cnt = 0; it = 1;
	while(it <= N*M){
		for(int i=1; i<=Z && it <= N*M; i++){
			if(tmp[it] > cnt) ans1++;
			it++;
		}
		cnt++;
	}
	printf("%d %d\n",ans1,ans2);

	return 0;
}

Compilation message

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

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9832 KB	Output is correct
2	Correct	0 ms	9832 KB	Output is correct
3	Correct	89 ms	17700 KB	Output is correct
4	Correct	76 ms	17728 KB	Output is correct
5	Correct	73 ms	17680 KB	Output is correct
6	Correct	86 ms	20728 KB	Output is correct
7	Correct	63 ms	17936 KB	Output is correct
8	Correct	53 ms	25464 KB	Output is correct
9	Correct	159 ms	52840 KB	Output is correct
10	Correct	69 ms	17700 KB	Output is correct
11	Correct	76 ms	17728 KB	Output is correct
12	Correct	76 ms	17680 KB	Output is correct
13	Correct	66 ms	20728 KB	Output is correct
14	Correct	66 ms	17936 KB	Output is correct
15	Correct	59 ms	25464 KB	Output is correct
16	Correct	149 ms	52840 KB	Output is correct
17	Correct	76 ms	17700 KB	Output is correct
18	Correct	79 ms	17728 KB	Output is correct
19	Correct	69 ms	17680 KB	Output is correct
20	Correct	83 ms	20728 KB	Output is correct
21	Correct	83 ms	17936 KB	Output is correct
22	Correct	63 ms	25464 KB	Output is correct
23	Correct	219 ms	52840 KB	Output is correct
24	Correct	419 ms	17700 KB	Output is correct
25	Correct	413 ms	17728 KB	Output is correct
26	Correct	409 ms	17680 KB	Output is correct
27	Correct	706 ms	20728 KB	Output is correct
28	Correct	509 ms	17936 KB	Output is correct
29	Correct	413 ms	25464 KB	Output is correct
30	Correct	806 ms	52840 KB	Output is correct
31	Correct	59 ms	17700 KB	Output is correct
32	Correct	116 ms	52840 KB	Output is correct