oj.uz

Submission #59881

# Submission time Handle Problem Language Result Execution time Memory
59881 2018-07-23T08:28:41 Z ainta(#1720) Cultivation (JOI17_cultivation) C++11
5 / 100
 297 ms 892 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[i].x - 1 + W - w[j].x);
				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[i].y - 1 + H - w[j].y);
				X.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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 5 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 6 ms 672 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 5 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 5 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 6 ms 672 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 5 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 42 ms 876 KB Output is correct
18 Correct 126 ms 876 KB Output is correct
19 Correct 297 ms 876 KB Output is correct
20 Correct 201 ms 892 KB Output is correct
21 Incorrect 228 ms 892 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 5 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 6 ms 672 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 5 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 42 ms 876 KB Output is correct
18 Correct 126 ms 876 KB Output is correct
19 Correct 297 ms 876 KB Output is correct
20 Correct 201 ms 892 KB Output is correct
21 Incorrect 228 ms 892 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 892 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 4 ms 892 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 Correct 4 ms 504 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 5 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 6 ms 672 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 5 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 42 ms 876 KB Output is correct
18 Correct 126 ms 876 KB Output is correct
19 Correct 297 ms 876 KB Output is correct
20 Correct 201 ms 892 KB Output is correct
21 Incorrect 228 ms 892 KB Output isn't correct
22 Halted 0 ms 0 KB -