답안 #414371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414371	2021-05-30T11:38:37 Z	amoo_safar	Cultivation (JOI17_cultivation)	C++17	15 / 100	729 ms	262148 KB

cultivation

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 3e2 + 10;
const int Inf = 2'000'000'001;
const ll Log = 30;

int n, R, C;
pii A[N];

// 0, x, y -> C + R < x -> y
// 1, x, y -> C < x -> y
// 2, x, y -> R < x -> y
typedef pii con;
typedef pair<con, int> Query;
vector<Query> Q, TQ, V0, V1;
typedef pair<con, con> iff;
vector< pair<iff, int> > cons;

bool Better(con A, con B){
	if(A.F != B.F)
		return false;
	return A.S >= B.S;
}
bool Better(iff A, iff B){
	return Better(A.F, B.F) && Better(A.S, B.S);
}
bool Sat(con A, int i, int j){
	if(A.F == 0)
		return i + j < A.S;
	if(A.F == 1)
		return i < A.S;
	return j < A.S;
}
void Check(int l, int r){
	int ln = r - l - 1;
	vector<int> V;
	for(int k = 1; k <= n; k++){
		if(l < A[k].F && A[k].F < r)
			V.pb(A[k].S);
	}
	sort(all(V));

	int sz = Q.size();
	vector< pair<con, int> > tmp;
	if(!V.empty() && V[0] > 1)
		tmp.pb({{1, V[0] - 1}, ln});
	if(!V.empty() && V.back() < C)
		tmp.pb({{2, C - V.back()}, ln});
	for(int i = 0; i + 1 < (int) V.size(); i++){
		if(0 < V[i + 1] - V[i] - 1)
			tmp.pb({{0, V[i + 1] - V[i] - 1}, ln});
	}
	if(V.empty())
		tmp.pb({{1, C}, ln});
	sort(all(tmp));
	int cnt = 0;
	for(int i = 0; i < (int) tmp.size(); i++)
		if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1].F, tmp[i].F)) )
			Q.pb(tmp[i]), cnt ++;
	// cerr << "!! " << ' ' << cnt << '\n';
	for(int i = sz; i < (int) Q.size(); i++)
		TQ.pb(Q[i]);
	// Q.resize(sz);
}

int ans[N][N]; // C R

pii Inter(pii A, pii B){ return pii(max(A.F, B.F), min(A.S, B.S)); }
pii Inter(con c, int v){
	if(c.F == 0){
		if(v < c.S)
			return pii(0, v + 1);
		return pii(v + 1, 0);
	} else if(c.F == 1){
		return pii(0, c.S);
	}
	return pii((v - c.S) + 1, v + 1);
}
pii Inter(iff c, int v){ return Inter(Inter(c.F, v), Inter(c.S, v)); }

vector<iff> act;
bool Valid(int v){
	// return false;
	vector<int> mk(v + 1, 0);
	// v = min(C - 1 + C - 1, v);
	// for(int i = 0, j = v; i < C; i++, j--)
	// 	if(0 <= j && j < C && ans[i][j] == 0)
	// 		return true;
	// return false;
	// vector<iff> tmp = act;
	// act.clear();
	// for(int i = 0; i < (int) tmp.size(); i++)
	// 	if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1], tmp[i])) )
	// 		act.pb(tmp[i]);
	
	pii seg = pii(0, C);
	if(v < C)
		seg = pii(0, v + 1);
	else
		seg = pii(v - (C - 1), C);
	// cerr << "!! " << v << ' ' << seg.F << ' ' << seg.S << '\n';

	vector<pii> Al;
	for(auto fi : act){
		pii X = Inter(fi, v);
		X = Inter(X, seg);
		// X.S = min(X.S, v + 1);
		// X.F = max(X.F, 0);
		if(X.F >= X.S) continue;
		Al.pb(X);
		for(int i = X.F; i < X.S; i++) mk[i] = 1;
	}
	sort(all(Al));
	int nw = seg.F;
	for(auto [l, r] : Al){
		if(nw < l)
			return true;
		nw = max(nw, r);
	}
	if(nw != seg.S)
		return true;
	return false;
	for(int i = 0; i <= v; i++){
		if(i < C && v - i < C && mk[i] == 0)
			return true;
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> R >> C >> n;
	for(int i = 1; i <= n; i++){
		cin >> A[i].F >> A[i].S;
	}
	sort(A + 1, A + n + 1);
	// vector<int> V;
	// sort(all(V));
	// for(int i = 1; i <= n; i++) V.pb(A[i].S);
	// int mn_S = 0;
	// for(int i = 0; i < n; i++)
	// 	mn_S = max(mn_S, V[i + 1] - V[i] - 1);
	// Check(0, R + 1);
	// int mx = (A[1].F - 1) + (R - A[n].F);
	Check(0, R + 1);
	for(auto &[cn, sm] : Q)
		sm = Inf;

	// debug(Q.size());

	TQ.clear();
	int sz = Q.size();
	for(int i = 1; i <= n; i++)
		Check(0, A[i].F);
	Q.resize(sz);
	V0 = TQ; TQ.clear();
	for(int i = 1; i <= n; i++)
		Check(A[i].F, R + 1);
	Q.resize(sz);
	V1 = TQ; TQ.clear();
	for(auto [c1, v1] : V0)
		for(auto [c2, v2] : V1)
			cons.pb({{min(c1, c2), max(c1, c2)}, v1 + v2});
	// debug(Q.size());
	Q.resize(sz);
	// debug(Q.size());

	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
			if(A[j].F - 1 > A[i].F)
				Check(A[i].F, A[j].F);
	// debug(Q.size());
	for(auto [c1, v1] : Q)
		cons.pb({{c1, c1}, v1});
	
	sort(all(cons), [&](auto e1, auto e2){
		return e1.S > e2.S;
	});
	// debug("X");
	// debug(cons.size());
	int ANS = R + C;
	cons.pb({{{0, 0}, {0, 0}}, 0});
	int la = -1;
	for(auto [fi, v] : cons){
		// debug(v);
		// int CC = C + C;
		// for(int i = 0; i < C; i++){
		// 	for(int j = 0; j < C; j++)
		// 		if(!ans[i][j])
		// 			// CC = min(CC, i + j);
		// 			ANS = min(ANS, i + j + v);
		// }
		if(la == v){
			act.pb(fi);
			continue;
		}
		int L = -1, Rb = C + C - 1;
		int mid;
		while(L + 1 < Rb){
			mid = (L + Rb) >> 1;
			if(Valid(mid)) Rb = mid;
			else L = mid;
		}
		if(Rb != C + C - 1)
			ANS = min(ANS, Rb + v);
		la = v;
		act.pb(fi);
	}
	
	cout << ANS << '\n';
	return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	324 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	324 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	25 ms	1172 KB	Output is correct
19	Correct	8 ms	540 KB	Output is correct
20	Correct	5 ms	460 KB	Output is correct
21	Correct	33 ms	1012 KB	Output is correct
22	Correct	89 ms	2904 KB	Output is correct
23	Correct	9 ms	672 KB	Output is correct
24	Correct	131 ms	4124 KB	Output is correct
25	Correct	144 ms	3784 KB	Output is correct
26	Correct	729 ms	21268 KB	Output is correct
27	Correct	245 ms	7272 KB	Output is correct
28	Correct	161 ms	5804 KB	Output is correct
29	Correct	166 ms	5552 KB	Output is correct
30	Correct	195 ms	6604 KB	Output is correct
31	Correct	272 ms	7860 KB	Output is correct
32	Correct	175 ms	5628 KB	Output is correct

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	324 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	25 ms	1172 KB	Output is correct
19	Correct	8 ms	540 KB	Output is correct
20	Correct	5 ms	460 KB	Output is correct
21	Correct	33 ms	1012 KB	Output is correct
22	Correct	89 ms	2904 KB	Output is correct
23	Correct	9 ms	672 KB	Output is correct
24	Correct	131 ms	4124 KB	Output is correct
25	Correct	144 ms	3784 KB	Output is correct
26	Correct	729 ms	21268 KB	Output is correct
27	Correct	245 ms	7272 KB	Output is correct
28	Correct	161 ms	5804 KB	Output is correct
29	Correct	166 ms	5552 KB	Output is correct
30	Correct	195 ms	6604 KB	Output is correct
31	Correct	272 ms	7860 KB	Output is correct
32	Correct	175 ms	5628 KB	Output is correct
33	Runtime error	143 ms	262148 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	107 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	107 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	324 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	25 ms	1172 KB	Output is correct
19	Correct	8 ms	540 KB	Output is correct
20	Correct	5 ms	460 KB	Output is correct
21	Correct	33 ms	1012 KB	Output is correct
22	Correct	89 ms	2904 KB	Output is correct
23	Correct	9 ms	672 KB	Output is correct
24	Correct	131 ms	4124 KB	Output is correct
25	Correct	144 ms	3784 KB	Output is correct
26	Correct	729 ms	21268 KB	Output is correct
27	Correct	245 ms	7272 KB	Output is correct
28	Correct	161 ms	5804 KB	Output is correct
29	Correct	166 ms	5552 KB	Output is correct
30	Correct	195 ms	6604 KB	Output is correct
31	Correct	272 ms	7860 KB	Output is correct
32	Correct	175 ms	5628 KB	Output is correct
33	Runtime error	143 ms	262148 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-