답안 #59870 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59870	2018-07-23T08:20:53 Z	윤교준(#1726)	Cultivation (JOI17_cultivation)	C++11	60 / 100	2000 ms	1656 KB

cultivation

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const bool debug = 0;
const int MAXN = 305;

struct EVT {
	EVT(int type, int y, int x)
		: type(type), y(y), x(x) {}
	int type, y, x;

	bool operator < (const EVT &t) const {
		if(x != t.x) return x < t.x;
		if(type != t.type) return type > t.type;
		return y < t.y;
	}
};

vector<int> LV, RV;

int A[MAXN], B[MAXN], C[MAXN];

ll Ans = INFLL;
int H, W, N, LX, RX;

int main() {
	ios::sync_with_stdio(false);

	cin >> H >> W >> N;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];

	swap(H, W);
	for(int i = 1; i <= N; i++) swap(A[i], B[i]);

	LX = *min_element(B+1, B+N+1) - 1;
	RX = W - *max_element(B+1, B+N+1);

	for(int i = 1; i <= N; i++) {
		int s = max(1, B[i]-LX), e = min(W, B[i]+RX);
		B[i] = s; C[i] = e;
	}

	LV.eb(0); RV.eb(0);
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
		int t = max(0, B[j]-C[i]-1);
		LV.eb(t); RV.eb(t);
	}
	for(int i = 1; i <= N; i++) LV.eb(B[i]-1);
	for(int i = 1; i <= N; i++) RV.eb(W-C[i]);
	sorv(LV); sorv(RV); univ(LV); univ(RV);

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("%d ; %d / %d %d\n", i, A[i], B[i], C[i]);
	}

	random_shuffle(allv(LV));

	for(int l : LV) {
		RV.clear();
		RV.eb(0);
		for(int i = 1; i <= N; i++) RV.eb(W-C[i]);
		for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
			int t = max(0, (max(1, B[j]-l) - C[i] - 1));
			RV.eb(t);
		}
		sorv(RV); univ(RV);

		random_shuffle(allv(RV));
		for(int r : RV) {

			multiset<int> CH;
			vector<EVT> EV;

			for(int i = 1, s, e; i <= N; i++) {
				s = max(1, B[i]-l), e = min(W, C[i]+r);
				EV.eb(1, A[i], s);
				EV.eb(0, A[i], e+1);
			}
			sorv(EV);
			CH.insert(0); CH.insert(H+1);

			if(debug) {
				printf("l=%d, r=%d\n", l, r);
				for(auto &ev : EV) printf("%d %d %d\n", ev.type, ev.x, ev.y);
			}

			int upd = 0, dwd = 0, mxs = 0;
			bool ismang = false;

			for(int i = 0, j, n = sz(EV); i < n; i = j) {
				for(j = i; j < n && EV[i].x == EV[j].x; j++) {
					if(Ans <= (ll)max(upd+dwd, mxs) + l + r) {
						ismang = true;
						break;
					}

					EVT &ev = EV[j];
					if(debug) printf("EVT %d ; %d %d\n", ev.type, ev.x, ev.y);
					if(W < ev.x) continue;
					if(ev.type) {
						CH.insert(ev.y);
						auto dit = prev(CH.lower_bound(ev.y));

						if(0 == *dit) upmax(dwd, ev.y - *dit - 1);
						else upmax(mxs, ev.y - *dit - 1);
					} else {
						CH.erase(CH.find(ev.y));
						if(CH.end() != CH.find(ev.y)) continue;

						auto dit = prev(CH.lower_bound(ev.y));
						auto uit = CH.upper_bound(ev.y);

						if(0 == *dit && H+1 == *uit) {
							upd = dwd = INF;
							continue;
						} else if(0 == *dit) upmax(dwd, *uit - *dit - 1);
						else if(H+1 == *uit) upmax(upd, *uit - *dit - 1);
						else upmax(mxs, *uit - *dit - 1);
					}
					if(debug) {
						for(int v : CH) printf("%d ", v);
						puts("");
						printf("upd=%d, dwd=%d, mxs=%d\n", upd, dwd, mxs);
					}
				}

				{
					auto it = prev(prev(CH.end()));
					if(0 == *it) upd = dwd = INF;
					else upmax(upd, H - *it);
				}

				if(Ans <= (ll)max(upd+dwd, mxs) + l + r) {
					ismang = true;
					break;
				}
				if(ismang) break;
			}

			if(H <= upd || H <= dwd) continue;

			upmin(Ans, (ll)max(upd+dwd, mxs) + l + r);
		}
	}

	cout << (Ans + LX + RX) << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	3 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	2 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	3 ms	728 KB	Output is correct
13	Correct	2 ms	728 KB	Output is correct
14	Correct	2 ms	728 KB	Output is correct
15	Correct	2 ms	728 KB	Output is correct
16	Correct	2 ms	736 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	3 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	2 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	3 ms	728 KB	Output is correct
13	Correct	2 ms	728 KB	Output is correct
14	Correct	2 ms	728 KB	Output is correct
15	Correct	2 ms	728 KB	Output is correct
16	Correct	2 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	14 ms	736 KB	Output is correct
19	Correct	6 ms	736 KB	Output is correct
20	Correct	4 ms	736 KB	Output is correct
21	Correct	18 ms	736 KB	Output is correct
22	Correct	48 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	106 ms	1260 KB	Output is correct
25	Correct	75 ms	1260 KB	Output is correct
26	Correct	239 ms	1516 KB	Output is correct
27	Correct	250 ms	1636 KB	Output is correct
28	Correct	117 ms	1636 KB	Output is correct
29	Correct	206 ms	1640 KB	Output is correct
30	Correct	207 ms	1640 KB	Output is correct
31	Correct	193 ms	1640 KB	Output is correct
32	Correct	237 ms	1640 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	3 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	2 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	3 ms	728 KB	Output is correct
13	Correct	2 ms	728 KB	Output is correct
14	Correct	2 ms	728 KB	Output is correct
15	Correct	2 ms	728 KB	Output is correct
16	Correct	2 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	14 ms	736 KB	Output is correct
19	Correct	6 ms	736 KB	Output is correct
20	Correct	4 ms	736 KB	Output is correct
21	Correct	18 ms	736 KB	Output is correct
22	Correct	48 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	106 ms	1260 KB	Output is correct
25	Correct	75 ms	1260 KB	Output is correct
26	Correct	239 ms	1516 KB	Output is correct
27	Correct	250 ms	1636 KB	Output is correct
28	Correct	117 ms	1636 KB	Output is correct
29	Correct	206 ms	1640 KB	Output is correct
30	Correct	207 ms	1640 KB	Output is correct
31	Correct	193 ms	1640 KB	Output is correct
32	Correct	237 ms	1640 KB	Output is correct
33	Correct	11 ms	1640 KB	Output is correct
34	Correct	245 ms	1640 KB	Output is correct
35	Correct	267 ms	1640 KB	Output is correct
36	Correct	278 ms	1640 KB	Output is correct
37	Correct	183 ms	1640 KB	Output is correct
38	Correct	250 ms	1640 KB	Output is correct
39	Correct	233 ms	1640 KB	Output is correct
40	Correct	244 ms	1640 KB	Output is correct
41	Correct	193 ms	1644 KB	Output is correct
42	Correct	270 ms	1644 KB	Output is correct
43	Correct	248 ms	1656 KB	Output is correct
44	Correct	237 ms	1656 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	1656 KB	Output is correct
2	Correct	194 ms	1656 KB	Output is correct
3	Correct	110 ms	1656 KB	Output is correct
4	Correct	329 ms	1656 KB	Output is correct
5	Correct	204 ms	1656 KB	Output is correct
6	Correct	39 ms	1656 KB	Output is correct
7	Correct	4 ms	1656 KB	Output is correct
8	Correct	45 ms	1656 KB	Output is correct
9	Correct	56 ms	1656 KB	Output is correct
10	Correct	132 ms	1656 KB	Output is correct
11	Correct	229 ms	1656 KB	Output is correct
12	Correct	95 ms	1656 KB	Output is correct
13	Correct	16 ms	1656 KB	Output is correct
14	Correct	75 ms	1656 KB	Output is correct
15	Correct	5 ms	1656 KB	Output is correct
16	Correct	136 ms	1656 KB	Output is correct
17	Correct	165 ms	1656 KB	Output is correct
18	Correct	7 ms	1656 KB	Output is correct
19	Correct	109 ms	1656 KB	Output is correct
20	Correct	38 ms	1656 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	1656 KB	Output is correct
2	Correct	194 ms	1656 KB	Output is correct
3	Correct	110 ms	1656 KB	Output is correct
4	Correct	329 ms	1656 KB	Output is correct
5	Correct	204 ms	1656 KB	Output is correct
6	Correct	39 ms	1656 KB	Output is correct
7	Correct	4 ms	1656 KB	Output is correct
8	Correct	45 ms	1656 KB	Output is correct
9	Correct	56 ms	1656 KB	Output is correct
10	Correct	132 ms	1656 KB	Output is correct
11	Correct	229 ms	1656 KB	Output is correct
12	Correct	95 ms	1656 KB	Output is correct
13	Correct	16 ms	1656 KB	Output is correct
14	Correct	75 ms	1656 KB	Output is correct
15	Correct	5 ms	1656 KB	Output is correct
16	Correct	136 ms	1656 KB	Output is correct
17	Correct	165 ms	1656 KB	Output is correct
18	Correct	7 ms	1656 KB	Output is correct
19	Correct	109 ms	1656 KB	Output is correct
20	Correct	38 ms	1656 KB	Output is correct
21	Execution timed out	2029 ms	1656 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	3 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	2 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	3 ms	728 KB	Output is correct
13	Correct	2 ms	728 KB	Output is correct
14	Correct	2 ms	728 KB	Output is correct
15	Correct	2 ms	728 KB	Output is correct
16	Correct	2 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	14 ms	736 KB	Output is correct
19	Correct	6 ms	736 KB	Output is correct
20	Correct	4 ms	736 KB	Output is correct
21	Correct	18 ms	736 KB	Output is correct
22	Correct	48 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	106 ms	1260 KB	Output is correct
25	Correct	75 ms	1260 KB	Output is correct
26	Correct	239 ms	1516 KB	Output is correct
27	Correct	250 ms	1636 KB	Output is correct
28	Correct	117 ms	1636 KB	Output is correct
29	Correct	206 ms	1640 KB	Output is correct
30	Correct	207 ms	1640 KB	Output is correct
31	Correct	193 ms	1640 KB	Output is correct
32	Correct	237 ms	1640 KB	Output is correct
33	Correct	11 ms	1640 KB	Output is correct
34	Correct	245 ms	1640 KB	Output is correct
35	Correct	267 ms	1640 KB	Output is correct
36	Correct	278 ms	1640 KB	Output is correct
37	Correct	183 ms	1640 KB	Output is correct
38	Correct	250 ms	1640 KB	Output is correct
39	Correct	233 ms	1640 KB	Output is correct
40	Correct	244 ms	1640 KB	Output is correct
41	Correct	193 ms	1644 KB	Output is correct
42	Correct	270 ms	1644 KB	Output is correct
43	Correct	248 ms	1656 KB	Output is correct
44	Correct	237 ms	1656 KB	Output is correct
45	Correct	24 ms	1656 KB	Output is correct
46	Correct	194 ms	1656 KB	Output is correct
47	Correct	110 ms	1656 KB	Output is correct
48	Correct	329 ms	1656 KB	Output is correct
49	Correct	204 ms	1656 KB	Output is correct
50	Correct	39 ms	1656 KB	Output is correct
51	Correct	4 ms	1656 KB	Output is correct
52	Correct	45 ms	1656 KB	Output is correct
53	Correct	56 ms	1656 KB	Output is correct
54	Correct	132 ms	1656 KB	Output is correct
55	Correct	229 ms	1656 KB	Output is correct
56	Correct	95 ms	1656 KB	Output is correct
57	Correct	16 ms	1656 KB	Output is correct
58	Correct	75 ms	1656 KB	Output is correct
59	Correct	5 ms	1656 KB	Output is correct
60	Correct	136 ms	1656 KB	Output is correct
61	Correct	165 ms	1656 KB	Output is correct
62	Correct	7 ms	1656 KB	Output is correct
63	Correct	109 ms	1656 KB	Output is correct
64	Correct	38 ms	1656 KB	Output is correct
65	Execution timed out	2029 ms	1656 KB	Time limit exceeded
66	Halted	0 ms	0 KB	-

답안 #59870

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 30.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
15.0 / 15.0

Subtask #4
30.0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0