Submission #1197495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197495		og_matveychick1	Cultivation (JOI17_cultivation)	C++20	0 / 100	1943 ms	448 KiB

cultivation

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;


const ll N = 305;

ll n, r, c, x[N], y[N], ans = 1e18;
vll cup;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> r >> c >> n;
    for (ll i = 0; i < n; i++) cin >> x[i] >> y[i], x[i]--, y[i]--;
    for (ll i = 0; i < n; i++) {
        for (ll j = i + 1; j < n; j++) {
            cup.push_back(abs(x[i] - x[j]));
            cup.push_back(abs(x[i] - x[j]) + 1);
            if (x[i] != x[j]) cup.push_back(abs(x[i] - x[j]) - 1);
        }
    }
    sort(cup.begin(), cup.end());
    cup.resize(unique(cup.begin(), cup.end()) - cup.begin());
    for (ll up = 0; up < cup.size(); up++) {
        for (ll dn = 0; dn < cup.size(); dn++) {
            ll mx = 0, L = 0, R = 0;
            vector<ll> cp;
            for (ll i = 0; i < n; i++) {
                for (ll j = -1; j <= 1; j++) {
                    cp.push_back(max(0ll, x[i] - cup[up] + j));
                    cp.push_back(min(r - 1, x[i] + cup[dn] + j));
                }
            }
            for (ll p = 0; p < cp.size(); p++) {
                vll a;
                for (ll i = 0; i < n; i++) if (x[i] - cup[up] <= cp[p] && x[i] + cup[dn] >= cp[p]) a.push_back(y[i]);
                sort(a.begin(), a.end());
                if (!a.size()) mx = 1e18;
                else {
                    L = max(L, a[0]), R = max(R, c - a.back() - 1);
                    for (int i = 0; i < a.size() - 1; i++) mx = max(mx, a[i + 1] - a[i] - 1);
                }
            }
            ans = min(ans, max(mx, L + R) + cup[dn] + cup[up]);
        }
    }
    cout << ans;
}

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