Submission #1150014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150014		jhwest2	Cultivation (JOI17_cultivation)	C++20	80 / 100	2095 ms	9972 KiB

cultivation

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 10;
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int r, c, n;
	cin >> r >> c >> n;

	vector<pii> V;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		V.push_back({--x, --y});
	}
	sort(V.begin(), V.end());

	int X[n], Y[n];
	for (int i = 0; i < n; i++) {
		tie(X[i], Y[i]) = V[i];
	}

	set<int> K;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (X[i] != X[j]) {
				K.insert(abs(X[i] - X[j]));
				K.insert(abs(X[i] - X[j]) + 1);
			}
			K.insert(X[i] + r - X[j]);
			K.insert(X[j] + r - X[i]);
		}
	}

	vector<vector<int>> S[3];
	for (int t = 0; t < 3; t++) {
		S[t] = vector<vector<int>>(n, vector<int>(n, 0));
	}

	for (int i = 0; i < n; i++) {
		multiset<int> st;
		int mx = 0;
		for (int j = i; j < n; j++) {
			st.insert(Y[j]);
		}
		int p = -1;
		for (int x : st) {
			if (p != -1) {
				mx = max(mx, x - p);
			}
			p = x;
		}

		for (int j = n - 1; j >= i; j--) {
			S[0][i][j] = *st.begin();
			S[1][i][j] = c - *prev(st.end());
			S[2][i][j] = mx;

			auto it = st.find(Y[j]);
			if (it != st.begin() && it != prev(st.end())) {
				mx = max(mx, *next(it) - *prev(it));
			}
			st.erase(it);
		}
	}

	auto calc = [&](ll k) {
		vector<ll> P;
		auto f = [&](ll x) {
			if (P.empty() || P.back() != x) {
				P.push_back(x);
			}
		};

		f(0);
		int q = 0;
		for (int i = 0; i < n; i++) {
			while (q < n && X[q] + k < X[i]) f(X[q++] + k);
			f(X[i]);
		}
		while (q < n) f(X[q++] + k);
		f(r + k - 1);

		int sz = P.size();
		vector<int> V[3];
		for (int t = 0; t < 3; t++) {
			V[t].resize(sz);
		}

		int s = 0, e = 0;
		for (int i = 1; i < sz; i++) {
			while (e < n && X[e] < P[i]) ++e;
			while (s < n && X[s] < P[i] - k) ++s;

			for (int t = 0; t < 3; t++) {
				V[t][i] = s < e ? S[t][s][e - 1] : max(1, t) * INF;
			}
		}
		
		vector<int> D[3];
		for (int t = 0; t < 3; t++) {
			D[t].resize(sz);
		}
		int ps[3]{}, pe[3]{};
		auto push = [&](int j) {
			for (int t = 0; t < 3; t++) {
				while (pe[t] > ps[t] && V[t][D[t][pe[t] - 1]] <= V[t][j]) {
					--pe[t];
				}
				D[t][pe[t]++] = j;
			}
		};
		auto pop = [&](int j) {
			for (int t = 0; t < 3; t++) {
				if (pe[t] > ps[t] && D[t][ps[t]] == j) {
					++ps[t];
				}
			}
		};
		
		s = 1;
		e = 1;
		auto get_sum = [&]() {
			return max(V[0][D[0][ps[0]]] + V[1][D[1][ps[1]]], V[2][D[2][ps[2]]]);
		};

		while (e < sz && P[e - 1] < r) push(e++);
		int mn = get_sum();
		
		while (true) {
			ll ts = P[s];
			ll te = P[e - 1] + 1 - r;
			if (min(ts, te) >= k) {
				break;
			}
			if (ts < te) {
				pop(s++);
			}
			else if (te < ts) {
				push(e++);
			}
			else {
				pop(s++);
				push(e++);
			}
			mn = min(mn, get_sum());
		}
		return (ll)k - 1 + mn - 1;
	};

	ll ans = r + c;
	for (int k : K) if (k - 1 < ans) ans = min(ans, calc(k));
	cout << ans << '\n';
}

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