Submission #414175

#	Time	Username	Problem	Language	Result	Execution time	Memory
414175		amoo_safar	Cultivation (JOI17_cultivation)	C++17	15 / 100	927 ms	15964 KiB

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 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));
	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]);

	for(int i = sz; i < (int) Q.size(); i++)
		TQ.pb(Q[i]);
	// Q.resize(sz);
}

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

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;

	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});
	Q.resize(sz);

	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);
	for(auto [c1, v1] : Q)
		cons.pb({{c1, c1}, v1});
	
	for(auto [fi, v] : cons){
		auto [c1, c2] = fi;
		for(int i = 0; i < C; i++)
			for(int j = 0; j < C; j++)
				if(Sat(c1, i, j) && Sat(c2, i, j))
					ans[i][j] = max(ans[i][j], v);
	}
	// }
	// for(int i = 0; i <= R; i++){
	// 	for(int j = i + 2; j <= R + 1; j++)
	// 		Check(i, j);
	// }
	// int mn_C = C, mn_R = C;
	// for(int i = 1; i <= n; i++)
	// 	mn_C = min(mn_C, A[i].S - 1), mn_R = min(mn_R, C - A[i].S);
	// for(int i = 0; i < C; i++)
	// 	for(int j = 0; j < C; j++)
	// 		ans[i][j] = mx;

	// for(auto [ty, el] : Q){
	// 	// cerr << "!!! " << ty << ' ' << el.F << " " << el.S << '\n';
	// 	if(ty == 0){
	// 		for(int i = 0; i < C; i++)
	// 			for(int j = 0; j < C; j++)
	// 				if(i + j < el.F)
	// 					ans[i][j] = max(ans[i][j], el.S);
	// 	} else if (ty == 1){
	// 		for(int i = 0; i < C; i++)
	// 			for(int j = 0; j < C; j++)
	// 				if(i < el.F)
	// 					ans[i][j] = max(ans[i][j], el.S);
	// 	} else {
	// 		for(int i = 0; i < C; i++)
	// 			for(int j = 0; j < C; j++)
	// 				if(j < el.F)
	// 					ans[i][j] = max(ans[i][j], el.S);
	// 	}
	// }

	// cerr << mn_C << ' ' << mn_R << ' ' << mn_S << '\n';
	int res = R + C;
	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){
			res = min(res, ans[i][j] + i + j);	
		}
	}
	cout << res << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20