답안 #59768 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59768	2018-07-23T05:18:36 Z	윤교준(#1726)	Cultivation (JOI17_cultivation)	C++11	30 / 100	332 ms	1824 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]);
	}

	for(int l : LV) {
		RV.clear();
		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);
		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;

			for(int i = 0, j, n = sz(EV); i < n; i = j) {
				for(j = i; j < n && EV[i].x == EV[j].x; j++) {
					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(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	248 KB	Output is correct
2	Correct	5 ms	360 KB	Output is correct
3	Correct	3 ms	440 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	656 KB	Output is correct
6	Correct	3 ms	708 KB	Output is correct
7	Correct	3 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	2 ms	708 KB	Output is correct
10	Correct	4 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	3 ms	708 KB	Output is correct
13	Correct	4 ms	708 KB	Output is correct
14	Correct	4 ms	708 KB	Output is correct
15	Correct	3 ms	708 KB	Output is correct
16	Correct	2 ms	708 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	5 ms	360 KB	Output is correct
3	Correct	3 ms	440 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	656 KB	Output is correct
6	Correct	3 ms	708 KB	Output is correct
7	Correct	3 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	2 ms	708 KB	Output is correct
10	Correct	4 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	3 ms	708 KB	Output is correct
13	Correct	4 ms	708 KB	Output is correct
14	Correct	4 ms	708 KB	Output is correct
15	Correct	3 ms	708 KB	Output is correct
16	Correct	2 ms	708 KB	Output is correct
17	Correct	4 ms	708 KB	Output is correct
18	Correct	16 ms	708 KB	Output is correct
19	Correct	8 ms	708 KB	Output is correct
20	Correct	3 ms	712 KB	Output is correct
21	Correct	18 ms	716 KB	Output is correct
22	Correct	69 ms	944 KB	Output is correct
23	Correct	5 ms	944 KB	Output is correct
24	Correct	128 ms	1364 KB	Output is correct
25	Correct	99 ms	1364 KB	Output is correct
26	Correct	249 ms	1628 KB	Output is correct
27	Correct	231 ms	1808 KB	Output is correct
28	Correct	127 ms	1808 KB	Output is correct
29	Correct	225 ms	1808 KB	Output is correct
30	Correct	209 ms	1808 KB	Output is correct
31	Correct	231 ms	1808 KB	Output is correct
32	Correct	254 ms	1808 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	5 ms	360 KB	Output is correct
3	Correct	3 ms	440 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	656 KB	Output is correct
6	Correct	3 ms	708 KB	Output is correct
7	Correct	3 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	2 ms	708 KB	Output is correct
10	Correct	4 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	3 ms	708 KB	Output is correct
13	Correct	4 ms	708 KB	Output is correct
14	Correct	4 ms	708 KB	Output is correct
15	Correct	3 ms	708 KB	Output is correct
16	Correct	2 ms	708 KB	Output is correct
17	Correct	4 ms	708 KB	Output is correct
18	Correct	16 ms	708 KB	Output is correct
19	Correct	8 ms	708 KB	Output is correct
20	Correct	3 ms	712 KB	Output is correct
21	Correct	18 ms	716 KB	Output is correct
22	Correct	69 ms	944 KB	Output is correct
23	Correct	5 ms	944 KB	Output is correct
24	Correct	128 ms	1364 KB	Output is correct
25	Correct	99 ms	1364 KB	Output is correct
26	Correct	249 ms	1628 KB	Output is correct
27	Correct	231 ms	1808 KB	Output is correct
28	Correct	127 ms	1808 KB	Output is correct
29	Correct	225 ms	1808 KB	Output is correct
30	Correct	209 ms	1808 KB	Output is correct
31	Correct	231 ms	1808 KB	Output is correct
32	Correct	254 ms	1808 KB	Output is correct
33	Correct	10 ms	1808 KB	Output is correct
34	Correct	189 ms	1808 KB	Output is correct
35	Correct	252 ms	1808 KB	Output is correct
36	Correct	263 ms	1808 KB	Output is correct
37	Correct	220 ms	1808 KB	Output is correct
38	Correct	281 ms	1808 KB	Output is correct
39	Correct	332 ms	1808 KB	Output is correct
40	Correct	259 ms	1808 KB	Output is correct
41	Correct	113 ms	1816 KB	Output is correct
42	Correct	220 ms	1816 KB	Output is correct
43	Correct	270 ms	1816 KB	Output is correct
44	Correct	232 ms	1824 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	1824 KB	Output is correct
2	Correct	53 ms	1824 KB	Output is correct
3	Correct	48 ms	1824 KB	Output is correct
4	Correct	46 ms	1824 KB	Output is correct
5	Correct	54 ms	1824 KB	Output is correct
6	Incorrect	25 ms	1824 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	1824 KB	Output is correct
2	Correct	53 ms	1824 KB	Output is correct
3	Correct	48 ms	1824 KB	Output is correct
4	Correct	46 ms	1824 KB	Output is correct
5	Correct	54 ms	1824 KB	Output is correct
6	Incorrect	25 ms	1824 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	5 ms	360 KB	Output is correct
3	Correct	3 ms	440 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	656 KB	Output is correct
6	Correct	3 ms	708 KB	Output is correct
7	Correct	3 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	2 ms	708 KB	Output is correct
10	Correct	4 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	3 ms	708 KB	Output is correct
13	Correct	4 ms	708 KB	Output is correct
14	Correct	4 ms	708 KB	Output is correct
15	Correct	3 ms	708 KB	Output is correct
16	Correct	2 ms	708 KB	Output is correct
17	Correct	4 ms	708 KB	Output is correct
18	Correct	16 ms	708 KB	Output is correct
19	Correct	8 ms	708 KB	Output is correct
20	Correct	3 ms	712 KB	Output is correct
21	Correct	18 ms	716 KB	Output is correct
22	Correct	69 ms	944 KB	Output is correct
23	Correct	5 ms	944 KB	Output is correct
24	Correct	128 ms	1364 KB	Output is correct
25	Correct	99 ms	1364 KB	Output is correct
26	Correct	249 ms	1628 KB	Output is correct
27	Correct	231 ms	1808 KB	Output is correct
28	Correct	127 ms	1808 KB	Output is correct
29	Correct	225 ms	1808 KB	Output is correct
30	Correct	209 ms	1808 KB	Output is correct
31	Correct	231 ms	1808 KB	Output is correct
32	Correct	254 ms	1808 KB	Output is correct
33	Correct	10 ms	1808 KB	Output is correct
34	Correct	189 ms	1808 KB	Output is correct
35	Correct	252 ms	1808 KB	Output is correct
36	Correct	263 ms	1808 KB	Output is correct
37	Correct	220 ms	1808 KB	Output is correct
38	Correct	281 ms	1808 KB	Output is correct
39	Correct	332 ms	1808 KB	Output is correct
40	Correct	259 ms	1808 KB	Output is correct
41	Correct	113 ms	1816 KB	Output is correct
42	Correct	220 ms	1816 KB	Output is correct
43	Correct	270 ms	1816 KB	Output is correct
44	Correct	232 ms	1824 KB	Output is correct
45	Correct	12 ms	1824 KB	Output is correct
46	Correct	53 ms	1824 KB	Output is correct
47	Correct	48 ms	1824 KB	Output is correct
48	Correct	46 ms	1824 KB	Output is correct
49	Correct	54 ms	1824 KB	Output is correct
50	Incorrect	25 ms	1824 KB	Output isn't correct
51	Halted	0 ms	0 KB	-

답안 #59768

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 15.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
15.0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0