oj.uz

Submission #447121

# Submission time Handle Problem Language Result Execution time Memory
447121 2021-07-24T15:50:00 Z alan8585 Cultivation (JOI17_cultivation) C++14
5 / 100
 8 ms 1476 KB 
#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 - 1;
            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(i == 0 && j == 2)
                // cout << ">>" << i << ' ' << j << ' ' << ln << ' ' << rn << '\n';
            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<int> Lm, Rm;
    for(int i = 0; i < n; i++) {
        Lm.pb(v[i].F - 1);
        // if(R - v[i].F >= R - rest)
        //     Rm.pb(R - v[i].F);
        // for(int j = i + 1; j < n; j++)
        //     if(abs(v[i].F - v[j].F) - 1 >= R - rest)
        //         Rm.pb(abs(v[i].F - v[j].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<int, int> m, dm, um;
        m[0] = 1;
        dm[0] = 1;
        um[0] = 1;
        // ll dldis = 0;
        // ll uldis = 0;
        vector<pair<ll, pll>> T;
        // m[0] += n;
        for(int j = 0; j < n; j++) {
            T.pb(MP(R - v[j].F, MP(0, 0)));
            // cout << v[j].F - << '\n';
        }
        for(int i = 0; i < n; i++) {
            // if(Dl[i] > lm) {
            //     dm[C - v[i].S]++;
            // }
            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() {
            //     cout << i << ' ' << v[i].S - 1 << ' ' << Ul[i] << '\n';
            //     um[v[i].S - 1]++;
            // }
            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]) continue;
                if(lm < L[i][j]) {
                    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])));
                } else {
                    m[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));
        // for(auto i : T) cout << i.F << ' ' << i.S.F << ' ' << i.S.S << '\n';
        // cout << '\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);
            }
            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) {
                // cout << minm << '\n';
                ll tans = lm + rm + max(m.rbegin() -> F, dm.rbegin() -> F + um.rbegin() -> F);
                // if(tans == 0) cout << '?' << '\n';
                ans = min(ans, tans);
            }
        }
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 2 ms 972 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 8 ms 1476 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 2 ms 972 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 8 ms 1476 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Incorrect 1 ms 580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Incorrect 1 ms 580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 2 ms 972 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 8 ms 1476 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -