Submission #59895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59895	2018-07-23T09:18:28 Z	ainta(#1720)	Cultivation (JOI17_cultivation)	C++11	15 / 100	794 ms	17672 KB

cultivation

#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);
			}
			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
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	416 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	6 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	10 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	9 ms	768 KB	Output is correct
8	Correct	9 ms	784 KB	Output is correct
9	Correct	5 ms	784 KB	Output is correct
10	Correct	4 ms	784 KB	Output is correct
11	Correct	1 ms	784 KB	Output is correct
12	Correct	6 ms	784 KB	Output is correct
13	Correct	5 ms	784 KB	Output is correct
14	Correct	5 ms	784 KB	Output is correct
15	Correct	6 ms	844 KB	Output is correct
16	Correct	6 ms	844 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	416 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	6 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	10 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	9 ms	768 KB	Output is correct
8	Correct	9 ms	784 KB	Output is correct
9	Correct	5 ms	784 KB	Output is correct
10	Correct	4 ms	784 KB	Output is correct
11	Correct	1 ms	784 KB	Output is correct
12	Correct	6 ms	784 KB	Output is correct
13	Correct	5 ms	784 KB	Output is correct
14	Correct	5 ms	784 KB	Output is correct
15	Correct	6 ms	844 KB	Output is correct
16	Correct	6 ms	844 KB	Output is correct
17	Correct	87 ms	844 KB	Output is correct
18	Correct	266 ms	844 KB	Output is correct
19	Correct	530 ms	844 KB	Output is correct
20	Correct	150 ms	912 KB	Output is correct
21	Correct	475 ms	916 KB	Output is correct
22	Correct	794 ms	916 KB	Output is correct
23	Correct	310 ms	920 KB	Output is correct
24	Correct	713 ms	920 KB	Output is correct
25	Correct	785 ms	920 KB	Output is correct
26	Correct	784 ms	920 KB	Output is correct
27	Correct	712 ms	920 KB	Output is correct
28	Correct	636 ms	920 KB	Output is correct
29	Correct	590 ms	920 KB	Output is correct
30	Correct	699 ms	920 KB	Output is correct
31	Correct	692 ms	920 KB	Output is correct
32	Correct	679 ms	920 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	416 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	6 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	10 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	9 ms	768 KB	Output is correct
8	Correct	9 ms	784 KB	Output is correct
9	Correct	5 ms	784 KB	Output is correct
10	Correct	4 ms	784 KB	Output is correct
11	Correct	1 ms	784 KB	Output is correct
12	Correct	6 ms	784 KB	Output is correct
13	Correct	5 ms	784 KB	Output is correct
14	Correct	5 ms	784 KB	Output is correct
15	Correct	6 ms	844 KB	Output is correct
16	Correct	6 ms	844 KB	Output is correct
17	Correct	87 ms	844 KB	Output is correct
18	Correct	266 ms	844 KB	Output is correct
19	Correct	530 ms	844 KB	Output is correct
20	Correct	150 ms	912 KB	Output is correct
21	Correct	475 ms	916 KB	Output is correct
22	Correct	794 ms	916 KB	Output is correct
23	Correct	310 ms	920 KB	Output is correct
24	Correct	713 ms	920 KB	Output is correct
25	Correct	785 ms	920 KB	Output is correct
26	Correct	784 ms	920 KB	Output is correct
27	Correct	712 ms	920 KB	Output is correct
28	Correct	636 ms	920 KB	Output is correct
29	Correct	590 ms	920 KB	Output is correct
30	Correct	699 ms	920 KB	Output is correct
31	Correct	692 ms	920 KB	Output is correct
32	Correct	679 ms	920 KB	Output is correct
33	Runtime error	158 ms	17672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	17672 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	17672 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	416 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	6 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	10 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	9 ms	768 KB	Output is correct
8	Correct	9 ms	784 KB	Output is correct
9	Correct	5 ms	784 KB	Output is correct
10	Correct	4 ms	784 KB	Output is correct
11	Correct	1 ms	784 KB	Output is correct
12	Correct	6 ms	784 KB	Output is correct
13	Correct	5 ms	784 KB	Output is correct
14	Correct	5 ms	784 KB	Output is correct
15	Correct	6 ms	844 KB	Output is correct
16	Correct	6 ms	844 KB	Output is correct
17	Correct	87 ms	844 KB	Output is correct
18	Correct	266 ms	844 KB	Output is correct
19	Correct	530 ms	844 KB	Output is correct
20	Correct	150 ms	912 KB	Output is correct
21	Correct	475 ms	916 KB	Output is correct
22	Correct	794 ms	916 KB	Output is correct
23	Correct	310 ms	920 KB	Output is correct
24	Correct	713 ms	920 KB	Output is correct
25	Correct	785 ms	920 KB	Output is correct
26	Correct	784 ms	920 KB	Output is correct
27	Correct	712 ms	920 KB	Output is correct
28	Correct	636 ms	920 KB	Output is correct
29	Correct	590 ms	920 KB	Output is correct
30	Correct	699 ms	920 KB	Output is correct
31	Correct	692 ms	920 KB	Output is correct
32	Correct	679 ms	920 KB	Output is correct
33	Runtime error	158 ms	17672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Halted	0 ms	0 KB	-

Submission #59895

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0