Submission #418850

#	Time	Username	Problem	Language	Result	Execution time	Memory
418850		Kevin_Zhang_TW	Cultivation (JOI17_cultivation)	C++17	15 / 100	1381 ms	460 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 305;

#define int ll
const int inf = 1ll << 55;
int R, C, n;
vector<pair<int,int>> loc;

bool can_cover(int ul, int dl, int al, int bl) {

	vector<vector<int>> pf_sum(50, vector<int> (50) );
	for (auto [x, y] : loc) {
		int A = y - ul, B = y + dl;
		int C = x - bl, D = x + al;
		chmax(A, 1ll);
		chmax(C, 1ll);
		chmin(D, R);
		chmin(B, ::C);
		++pf_sum[C][A];
		--pf_sum[D+1][A];
		--pf_sum[C][B+1];
		++pf_sum[D+1][B+1];
	}

	for (int i = 1;i <= R;++i) {
		for (int j = 1;j <= C;++j) {
			pf_sum[i][j] += pf_sum[i-1][j] + pf_sum[i][j-1] - pf_sum[i-1][j-1];
			if (pf_sum[i][j] == 0) return false;
		}
	}
	return true;
}

//int cal_up(int ul) {
//	int dnmn = 0;
//	{
//		vector<int> ys;
//		for (auto [x, y] : loc)
//			ys.pb(y - ul);
//		sort(AI(ys));
//		int lst_end = 0;
//		for (int y : ys) {
//			chmax(dnmn, y - 1 - lst_end);
//			lst_end = y + ul;
//		}
//		chmax(dnmn, C - lst_end);
//	}
//
//	vector<vector<tuple<int,int,int>>> op2, must;
//	vector<int> sep;
//
//	DE(ul);
//	auto all_op = [&]() {
//		op2.pb();
//		must.pb();
//		sort(AI(loc));
//
//		for (int i = 0;i < n;++i) {
//			auto [x, y] = loc[i];
//
//			DE(" gen ------------ ", x, y);
//			auto segmx = [&](int l, int r, int v) {
//				chmax(l, dnmn);
//				chmin(r, C);
//				if (l > r) return;
//				DE("segmx", l, r, v - x - 1);
//
//				sep.pb(l), sep.pb(r+1);
//				op2.back().pb(l, r+1, v - x - 1);
//			};
//			auto allmx = [&](int l, int r, int v) {
//				chmax(l, dnmn);
//				chmin(r, C);
//				if (l > r) return;
//				DE("mustmx", l, r, v - x - 1);
//
//				sep.pb(l), sep.pb(r+1);
//				must.back().pb(l, r+1, v - x - 1);
//			};
//
//			set<int> ys;
//			ys.insert(-inf);
//			ys.insert(inf);
//
//			int nl = 1, nr = C;
//			for (int j = i+1;j < n;++j) {
//				auto [cx, cy] = loc[j];
//				if (cx == x) continue;
//
//				if (cy <= y) chmax(nl, cy + 1);
//				if (cy >= y) chmin(nr, cy - ul - 1);
//
//				DE(cx, cy);
//				auto it = ys.lower_bound(cy);
//				int ly = *prev(it), ry = *it;  ys.insert(cy);
//				int s = -1, e = min(C - ly - 1, (ry - ul - 1) - ly - 1);
//				if (y <= ly || y >= ry) continue;
//				if (cy >= y) s = max<ll>(0, cy - ul - y);
//				else s = max<ll>(0, y - ul - cy);
//				segmx(s, e, cx);
//			}
//
//			DE(nl, nr);
//
//			if (nl > nr) continue;
//			if (nl == 1) allmx(0, C, R + 1);
//			else if (nl <= nr) allmx(0, nr - nl, R + 1);
//
//		}
//
//		DE(op2.size());
//		for (auto [l, r, v] : op2.back()) {
//			DE(l, r, v);
//		}
//   	};
//
//	all_op();
//	for (auto &[x, y] : loc) 
//		x = R - x + 1;
//
//	all_op();
//	for (auto &[x, y] : loc) 
//		x = R - x + 1;
//
//	sep.pb(C+1);
//
//	sort(AI(sep)); sep.erase(unique(AI(sep)), end(sep));
//
//	priority_queue<pair<int,int>> pq[2], pq2[2];
//	sort(AI(op2[0]));
//	sort(AI(op2[1]));
//	sort(AI(must[0]));
//	sort(AI(must[1]));
//
//	int h[2]{}, h2[2]{};
//
//	int res = inf;
//	for (int i = 0;i+1 < sep.size();++i) {
//		auto add_in = [&](auto &pq, auto &op, int &i) {
//			for (;i < op.size();++i) {
//				auto [l, r, v] = op[i];
//				if (l > sep[i]) break;
//				pq.emplace(v, r);
//			}
//		};
//		auto pops = [&](auto &pq) -> ll{
//			while (pq.size() && pq.top().second <= sep[i])
//				pq.pop();
//			return pq.size() ? pq.top().first : 0;
//		};
//
//		add_in(pq[0], op2[0], h[0]);
//		add_in(pq[1], op2[1], h[1]);
//		add_in(pq2[0], must[0], h2[0]);
//		add_in(pq2[1], must[1], h2[1]);
//
//
//		DE(sep[i], ul, 
//				max(pops(pq[0]), pops(pq[1])), pops(pq2[0]) + pops(pq2[1]));
//
//		int ld = pops(pq2[0]), rd = max(pops(pq2[1]), max(pops(pq[0]), pops(pq[1])) - ld), dn = sep[i];
//
//		assert(can_cover(ld, rd, ul, dn));
//
//		chmin(res, sep[i] + ul +
//				max({pops(pq[0]), pops(pq[1]), pops(pq2[0]) + pops(pq2[1])}));
//
//	}
//	DE(ul, res);
//	return res;
//}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> R >> C >> n; loc.resize(n);
	for (auto &[x, y] : loc) {
		cin >> x >> y;
	}
	sort(AI(loc));

	int res = inf;

	vector<int> ys;
	for (auto [x, y] : loc) ys.pb(y);


	for (int ul = 0;ul <= C;++ul) for (int dl = 0;dl <= C;++dl) {
		int A = R, B = R;
		while (B > 0 && can_cover(ul, dl, A, B-1)) --B;
		while (A > 0 && can_cover(ul, dl, A-1, B)) --A;
		if (can_cover(ul, dl, A, B))
			chmin(res, ul + dl + A + B);
	}

	// location should be the same
//	for (int y : ys) {
//		chmin(res, cal_up(y - 1));
//	}

	cout << res << '\n';
}

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