제출 #447136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447136		alan8585	Cultivation (JOI17_cultivation)	C++14	100 / 100	222 ms	3736 KiB

cultivation

#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

const int MAXN = 310;
const ll INF = 1LL << 61;
ll R, C, n, L[MAXN][MAXN], L_lim[MAXN][MAXN], R_lim[MAXN][MAXN], dis[MAXN][MAXN], ans = INF;
ll Ur[MAXN], Dr[MAXN], Ul[MAXN], Dl[MAXN];
vector<pll> v;

int main() {Tie
    cin >> R >> C >> n;
    v.resize(n);
    ll rest = 0;
    for(pll &i : v)
        cin >> i.F >> i.S, rest = max(rest, i.F);
    vector<pll> tv = v;
    sort(ALL(tv));
    ll minm = 0;
    for(int i = 0; i + 1 < n; i++)
        minm = max(minm, tv[i + 1].F - tv[i].F - 1);

    for(int i = 0; i < n; i++) {
        Dl[i] = Dr[i] = Ul[i] = Ur[i] = INF;
        {
            ll uln = 0;
            ll urn = R + 1;
            ll dln = 0;
            ll drn = R + 1;
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                if(v[i].S < v[j].S) {
                    if(v[i].F < v[j].F) {
                        drn = min(drn, v[j].F);
                    } else if(v[i].F > v[j].F) {
                        dln = max(dln, v[j].F);
                    } else {
                        Dl[i] = Dr[i] = -1;
                    }
                } else if(v[i].S > v[j].S) {
                    if(v[i].F < v[j].F) {
                        urn = min(urn, v[j].F);
                    } else if(v[i].F > v[j].F) {
                        uln = max(uln, v[j].F);
                    } else {
                        Ul[i] = Ur[i] = -1;
                    }
                }
            }
            if(Dl[i] != -1) {
                if(dln != 0) {
                    Dr[i] = drn - dln - 1;
                } else {
                    Dr[i] = INF;
                }
                if(drn != R + 1) {
                    Dl[i] = drn - dln - 1;
                } else {
                    Dl[i] = INF;
                }
            }
            if(Ul[i] != -1) {
                if(uln != 0) {
                    Ur[i] = urn - uln - 1;
                } else {
                    Ur[i] = INF;
                }
                if(urn != R + 1) {
                    Ul[i] = urn - uln - 1;
                } else {
                    Ul[i] = INF;
                }
            }
        }

        for(int j = i + 1; j < n; j++) {
            ll l = min(v[i].F, v[j].F);
            ll r = max(v[i].F, v[j].F);
            ll u = min(v[i].S, v[j].S);
            ll d = max(v[i].S, v[j].S);
            L[i][j] = r - l;
            dis[i][j] = d - u - 1;
            ll ln = 0;
            ll rn = R + 1;
            for(int k = 0; k < n; k++) {
                if(u < v[k].S && v[k].S < d) {
                    if(l <= v[k].F && v[k].F <= r)
                        L_lim[i][j] = R_lim[i][j] = -1;
                    else if(v[k].F < l)
                        ln = max(ln, v[k].F);
                    else if(v[k].F > l)
                        rn = min(rn, v[k].F);
                }
            }
            if(L_lim[i][j] == -1) continue;
            if(rn != R + 1)
                L_lim[i][j] = rn - ln - 1;
            else
                L_lim[i][j] = INF;
            if(ln != 0)
                R_lim[i][j] = rn - ln - 1;
            else
                R_lim[i][j] = INF;
        }
    }

    vector<ll> Lm, Rm;
    for(int i = 0; i < n; i++)
        Lm.pb(v[i].F - 1);
    sort(ALL(Lm)), Lm.resize(unique(ALL(Lm)) - Lm.begin());
    sort(ALL(Rm)), Rm.resize(unique(ALL(Rm)) - Rm.begin());

    for(ll lm : Lm) {
        map<ll, ll> m, dm, um;
        m[0] = 1;
        dm[0] = 1;
        um[0] = 1;
        vector<pair<ll, pll>> T;
        for(int j = 0; j < n; j++) {
            T.pb(MP(R - v[j].F, MP(0, 0)));
        }
        T.pb(MP(minm - lm, MP(0, 0)));
        for(int i = 0; i < n; i++) {
            if(Dr[i] != -1 && Dl[i] > lm) {
                dm[C - v[i].S]++;
                if(Dl[i] == Dr[i] && Dr[i] != INF)
                    T.pb(MP(Dr[i] - lm, MP(1, C - v[i].S)));
                else if(Dr[i] != INF)
                    T.pb(MP(Dr[i], MP(1, C - v[i].S)));
            }
            if(Ur[i] != -1 && Ul[i] > lm) {
                um[v[i].S - 1]++;
                if(Ul[i] == Ur[i] && Ur[i] != INF)
                    T.pb(MP(Ur[i] - lm, MP(2, v[i].S - 1)));
                else if(Ur[i] != INF)
                    T.pb(MP(Ur[i], MP(2, v[i].S - 1)));
            }
            for(int j = i + 1; j < n; j++) {
                if(L_lim[i][j] <= lm) continue;
                if(dis[i][j] <= 0) continue;
                T.pb(MP(L[i][j] - lm, MP(0, dis[i][j])));
                if(L_lim[i][j] == R_lim[i][j] && R_lim[i][j] != INF)
                    T.pb(MP(R_lim[i][j] - lm, MP(0, -dis[i][j])));
                else if(R_lim[i][j] != INF)
                    T.pb(MP(R_lim[i][j], MP(0, -dis[i][j])));
            }
        }
        sort(ALL(T));
        // cout << lm << '\n';
        // for(auto i : T) cout << i.S.F << ' ' << i.F << ' ' << i.S.S << '\n';
        int flag = 0, top = 0;
        while(top < (int)T.size()) {
            if(flag || T[top].F <= R - rest) {
                do {
                    if(T[top].S.F == 0) {
                        if(T[top].S.S < 0) {
                            m[-T[top].S.S]--;
                        } else if(T[top].S.S > 0) {
                            m[T[top].S.S]++;
                        }
                    } else if(T[top].S.F == 1) {
                        dm[T[top].S.S]--;
                    } else {
                        um[T[top].S.S]--;
                    }
                    top++;
                } while(top < (int)T.size() && (T[top].F == T[top - 1].F || T[top].F <= R - rest));
            }
            flag = 1;
            while(m.rbegin() -> S == 0) {
                auto p = m.end(); p--;
                m.erase(p);
            }
            while(dm.rbegin() -> S == 0) {
                auto p = dm.end(); p--;
                dm.erase(p);
            }
            while(um.rbegin() -> S == 0) {
                auto p = um.end(); p--;
                um.erase(p);
            }
            ll rm = 0;
            if(top - 1 >= 0)
                rm = max(rm, T[top - 1].F);
                // cout << lm << ' ' << rm << ' ' << m.rbegin() -> F << ' ' << dm.rbegin() -> F << ' ' << um.rbegin() -> F << '\n';
            if(lm + rm >= minm && rm >= R - rest) {
                ll tans = lm + rm + max(m.rbegin() -> F, dm.rbegin() -> F + um.rbegin() -> F);
                ans = min(ans, tans);
            }
        }
    }
    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: 20 / 20