oj.uz

답안 #414376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414376 2021-05-30T11:41:09 Z amoo_safar Cultivation (JOI17_cultivation) C++17
15 / 100
 2000 ms 33768 KB 
// 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 204 KB Output is correct
7 Correct 1 ms 204 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 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 204 KB Output is correct
7 Correct 1 ms 204 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 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 27 ms 1148 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 7 ms 460 KB Output is correct
21 Correct 32 ms 1048 KB Output is correct
22 Correct 109 ms 2996 KB Output is correct
23 Correct 9 ms 680 KB Output is correct
24 Correct 130 ms 4176 KB Output is correct
25 Correct 132 ms 3692 KB Output is correct
26 Correct 757 ms 21292 KB Output is correct
27 Correct 249 ms 7380 KB Output is correct
28 Correct 163 ms 5788 KB Output is correct
29 Correct 187 ms 5704 KB Output is correct
30 Correct 196 ms 6552 KB Output is correct
31 Correct 269 ms 7776 KB Output is correct
32 Correct 177 ms 5692 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 204 KB Output is correct
7 Correct 1 ms 204 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 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 27 ms 1148 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 7 ms 460 KB Output is correct
21 Correct 32 ms 1048 KB Output is correct
22 Correct 109 ms 2996 KB Output is correct
23 Correct 9 ms 680 KB Output is correct
24 Correct 130 ms 4176 KB Output is correct
25 Correct 132 ms 3692 KB Output is correct
26 Correct 757 ms 21292 KB Output is correct
27 Correct 249 ms 7380 KB Output is correct
28 Correct 163 ms 5788 KB Output is correct
29 Correct 187 ms 5704 KB Output is correct
30 Correct 196 ms 6552 KB Output is correct
31 Correct 269 ms 7776 KB Output is correct
32 Correct 177 ms 5692 KB Output is correct
33 Correct 440 ms 21160 KB Output is correct
34 Execution timed out 2037 ms 33768 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 321 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 321 ms 460 KB Output isn't correct
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 204 KB Output is correct
7 Correct 1 ms 204 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 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 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 27 ms 1148 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 7 ms 460 KB Output is correct
21 Correct 32 ms 1048 KB Output is correct
22 Correct 109 ms 2996 KB Output is correct
23 Correct 9 ms 680 KB Output is correct
24 Correct 130 ms 4176 KB Output is correct
25 Correct 132 ms 3692 KB Output is correct
26 Correct 757 ms 21292 KB Output is correct
27 Correct 249 ms 7380 KB Output is correct
28 Correct 163 ms 5788 KB Output is correct
29 Correct 187 ms 5704 KB Output is correct
30 Correct 196 ms 6552 KB Output is correct
31 Correct 269 ms 7776 KB Output is correct
32 Correct 177 ms 5692 KB Output is correct
33 Correct 440 ms 21160 KB Output is correct
34 Execution timed out 2037 ms 33768 KB Time limit exceeded
35 Halted 0 ms 0 KB -