Submission #28421

# Submission time Handle Problem Language Result Execution time Memory
28421 2017-07-16T05:37:02 Z AcornCkiGuiziTeam(#1202, dotorya, cki86201, zigui) Oriental P.A.D.A.K (FXCUP2_padak) C++14
0 / 1
89 ms 65536 KB
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:1048576")  
using namespace std;

#define mp make_pair  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef tuple <int, int, int> t3;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)

vector <int> dis[1000050];
vector <pii> Vu;

int* cnt;
int* ocnt;
int main() {
	int N, M, K, B, Z, i, j;
	scanf("%d %d %d %d %d", &N, &M, &K, &B, &Z);
	for (i = 0; i < N; i++) {
		dis[i].reserve(M);
		for (j = 0; j < M; j++) dis[i].push_back(INF);
	}

	Vu.reserve(N*M);
	while (K--) {
		scanf("%d %d", &i, &j);
		dis[i - 1][j - 1] = 0;
		Vu.emplace_back(i - 1, j - 1);
	}
	for (i = 0; i < Vu.size(); i++) {
		int d = dis[Vu[i].first][Vu[i].second];
		for (j = 0; j < 4; j++) {
			int x = Vu[i].first + "1102"[j] - '1';
			int y = Vu[i].second + "0211"[j] - '1';
			if (x < 0 || x >= N || y < 0 || y >= M || dis[x][y] != INF) continue;
			dis[x][y] = d + 1;
			Vu.emplace_back(x, y);
		}
	}
	Vu.clear();
	{
		vector <pii> Vu2;
		swap(Vu, Vu2);
	}

	cnt = new int[2000050];
	ocnt = new int[2000050];
	for (i = 0; i < 2000050; i++) ocnt[i] = cnt[i] = 0;
	for (i = 0; i < N; i++) for (j = 0; j < M; j++) ocnt[dis[i][j]]++;

	int a1 = 0, a2 = 0;

	int p = 1;
	for (i = 0; i <= 2000000; i++) cnt[i] = ocnt[i];
	for (i = 1; i <= 2000000; i++) {
		if (p < i) p = i;
		int t = Z;
		while (p <= 2000000 && t) {
			int x = min(t, cnt[p]);
			a2 += x;
			cnt[p] -= x;
			t -= x;
			if (cnt[p] == 0) p++;
		}
	}

	p = 2000000;
	for (i = 0; i <= 2000000; i++) cnt[i] = ocnt[i];
	for (i = 1; i <= 2000000; i++) {
		int t = Z;
		while (p >= i && t) {
			int x = min(t, cnt[p]);
			a1 += x;
			cnt[p] -= x;
			t -= x;
			if (cnt[p] == 0) p--;
		}
	}
	return !printf("%d %d\n", a1, a2);
}

Compilation message

padak.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
padak.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1048576")  
 ^
padak.cpp: In function 'int main()':
padak.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vu.size(); i++) {
                ^
padak.cpp:57: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:65:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &i, &j);
                         ^
# Verdict Execution time Memory Grader output
1 Correct 36 ms 41088 KB Output is correct
2 Correct 33 ms 41088 KB Output is correct
3 Correct 79 ms 45080 KB Output is correct
4 Correct 63 ms 45080 KB Output is correct
5 Correct 83 ms 45068 KB Output is correct
6 Correct 89 ms 45844 KB Output is correct
7 Correct 86 ms 45064 KB Output is correct
8 Correct 53 ms 45064 KB Output is correct
9 Memory limit exceeded 86 ms 65536 KB Memory limit exceeded
10 Halted 0 ms 0 KB -