oj.uz

Submission #59900

# Submission time Handle Problem Language Result Execution time Memory
59900 2018-07-23T09:31:38 Z ainta(#1720) Cultivation (JOI17_cultivation) C++11
0 / 100
 4 ms 744 KB 
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
int W, H, n,  S[130][130], M[130][130], D[130][130];
set<int>X, Y;
struct point {
	int x, y;
}w[330];
bool Pos(int dx, int dy) {
	int i, j;
	for (i = 0; i < 130; i++)for (j = 0; j < 130; j++)S[i][j] = 0;
	for (i = 1; i <= n; i++) {
		S[w[i].x][w[i].y]++;
		S[w[i].x][w[i].y+dy+1]--;
		S[w[i].x+dx+1][w[i].y]--;
		S[w[i].x+dx+1][w[i].y+dy+1]++;
	}
	for (i = 1; i < 130; i++)for (j = 1; j < 130; j++)S[i][j] += S[i][j - 1];
	for (i = 1; i < 130; i++)for (j = 1; j < 130; j++)S[i][j] += S[i-1][j];
	for (i = 1; i < 130; i++) {
		for (j = 1; j < 130; j++) {
			if (!S[i][j])M[i][j] = 0;
			else M[i][j] = M[i][j - 1] + 1;
		}
	}
	for (i = 1; i < 130; i++) {
		for (j = 1; j < 130; j++) {
			if (M[i][j] < H)D[i][j] = 0;
			else D[i][j] = D[i - 1][j] + 1;
			if (D[i][j] >= W) {
				return true;
			}
		}
	}
	return false;
}
int main() {
	
	int i, j;
	scanf("%d%d%d", &W, &H, &n);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].x, &w[i].y);
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (w[i].x <= w[j].x) {
				if(w[j].x>w[i].x)X.insert(w[j].x - w[i].x - 1);
			}
			X.insert(w[j].x - w[i].x + W);
			if (w[i].y <= w[j].y) {
				if (w[j].y>w[i].y)Y.insert(w[j].y - w[i].y - 1);
			}
			Y.insert(w[j].y - w[i].y + H);
		}
	}
	int res = 1e9;
	for (auto &x : X) {
		for (auto &y : Y) {
			if (Pos(x, y)) {
				res = min(res, x + y);
			}
		}
	}
	printf("%d\n", res);
	return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].x, &w[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -