Submission #59874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59874	2018-07-23T08:25:04 Z	윤교준(#1726)	Cultivation (JOI17_cultivation)	C++11	30 / 100	285 ms	1660 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) {
		vector<int> V;
		for(int i = 1; i <= N; i++) {
			V.eb(max(1, B[i]-l));
			V.eb(C[i]);
		}
		sorv(V); univ(V);

		RV.clear();
		RV.eb(0);
		for(int i = 1; i <= N; i++) RV.eb(W-C[i]);
		for(int i = 1, n = sz(V); i < n; i++) RV.eb(V[i]-V[i-1]-1);

		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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	252 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	3 ms	736 KB	Output is correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	3 ms	736 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	252 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	3 ms	736 KB	Output is correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	3 ms	736 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	20 ms	736 KB	Output is correct
19	Correct	7 ms	736 KB	Output is correct
20	Correct	4 ms	752 KB	Output is correct
21	Correct	19 ms	752 KB	Output is correct
22	Correct	69 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	148 ms	1276 KB	Output is correct
25	Correct	103 ms	1276 KB	Output is correct
26	Correct	228 ms	1580 KB	Output is correct
27	Correct	231 ms	1584 KB	Output is correct
28	Correct	139 ms	1584 KB	Output is correct
29	Correct	204 ms	1588 KB	Output is correct
30	Correct	229 ms	1588 KB	Output is correct
31	Correct	220 ms	1588 KB	Output is correct
32	Correct	232 ms	1588 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	252 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	3 ms	736 KB	Output is correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	3 ms	736 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	20 ms	736 KB	Output is correct
19	Correct	7 ms	736 KB	Output is correct
20	Correct	4 ms	752 KB	Output is correct
21	Correct	19 ms	752 KB	Output is correct
22	Correct	69 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	148 ms	1276 KB	Output is correct
25	Correct	103 ms	1276 KB	Output is correct
26	Correct	228 ms	1580 KB	Output is correct
27	Correct	231 ms	1584 KB	Output is correct
28	Correct	139 ms	1584 KB	Output is correct
29	Correct	204 ms	1588 KB	Output is correct
30	Correct	229 ms	1588 KB	Output is correct
31	Correct	220 ms	1588 KB	Output is correct
32	Correct	232 ms	1588 KB	Output is correct
33	Correct	11 ms	1588 KB	Output is correct
34	Correct	194 ms	1656 KB	Output is correct
35	Correct	285 ms	1656 KB	Output is correct
36	Correct	284 ms	1656 KB	Output is correct
37	Correct	195 ms	1656 KB	Output is correct
38	Correct	254 ms	1656 KB	Output is correct
39	Correct	249 ms	1656 KB	Output is correct
40	Correct	265 ms	1656 KB	Output is correct
41	Correct	131 ms	1656 KB	Output is correct
42	Correct	204 ms	1656 KB	Output is correct
43	Correct	277 ms	1656 KB	Output is correct
44	Correct	258 ms	1660 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1660 KB	Output is correct
2	Correct	101 ms	1660 KB	Output is correct
3	Correct	85 ms	1660 KB	Output is correct
4	Correct	85 ms	1660 KB	Output is correct
5	Correct	119 ms	1660 KB	Output is correct
6	Incorrect	38 ms	1660 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1660 KB	Output is correct
2	Correct	101 ms	1660 KB	Output is correct
3	Correct	85 ms	1660 KB	Output is correct
4	Correct	85 ms	1660 KB	Output is correct
5	Correct	119 ms	1660 KB	Output is correct
6	Incorrect	38 ms	1660 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	252 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	652 KB	Output is correct
10	Correct	2 ms	652 KB	Output is correct
11	Correct	2 ms	652 KB	Output is correct
12	Correct	3 ms	736 KB	Output is correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	3 ms	736 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct
17	Correct	4 ms	736 KB	Output is correct
18	Correct	20 ms	736 KB	Output is correct
19	Correct	7 ms	736 KB	Output is correct
20	Correct	4 ms	752 KB	Output is correct
21	Correct	19 ms	752 KB	Output is correct
22	Correct	69 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	148 ms	1276 KB	Output is correct
25	Correct	103 ms	1276 KB	Output is correct
26	Correct	228 ms	1580 KB	Output is correct
27	Correct	231 ms	1584 KB	Output is correct
28	Correct	139 ms	1584 KB	Output is correct
29	Correct	204 ms	1588 KB	Output is correct
30	Correct	229 ms	1588 KB	Output is correct
31	Correct	220 ms	1588 KB	Output is correct
32	Correct	232 ms	1588 KB	Output is correct
33	Correct	11 ms	1588 KB	Output is correct
34	Correct	194 ms	1656 KB	Output is correct
35	Correct	285 ms	1656 KB	Output is correct
36	Correct	284 ms	1656 KB	Output is correct
37	Correct	195 ms	1656 KB	Output is correct
38	Correct	254 ms	1656 KB	Output is correct
39	Correct	249 ms	1656 KB	Output is correct
40	Correct	265 ms	1656 KB	Output is correct
41	Correct	131 ms	1656 KB	Output is correct
42	Correct	204 ms	1656 KB	Output is correct
43	Correct	277 ms	1656 KB	Output is correct
44	Correct	258 ms	1660 KB	Output is correct
45	Correct	25 ms	1660 KB	Output is correct
46	Correct	101 ms	1660 KB	Output is correct
47	Correct	85 ms	1660 KB	Output is correct
48	Correct	85 ms	1660 KB	Output is correct
49	Correct	119 ms	1660 KB	Output is correct
50	Incorrect	38 ms	1660 KB	Output isn't correct
51	Halted	0 ms	0 KB	-

Submission #59874

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