Submission #1087405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087405		pokmui9909	Cultivation (JOI17_cultivation)	C++17	100 / 100	1898 ms	4836 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
#define x first
#define y second
ll H, W, N, F[3][305][305];
pair<ll, ll> A[305];

struct Data{
    ll l, r, c[3];
};

ll Add[605], Del[605];

ll Solve(ll len){
    for(ll i = 0; i <= 2 * N; i++){
        Add[i] = Del[i] = 0;
    }
    vector<ll> Num;
    A[N + 1].x = 1e18;
    for(ll i = 1, j = 1; j <= N;){
        if(A[i].x < A[j].x + len + 1){
            Num.push_back(A[i].x);
            i++;
        } else {
            Num.push_back(A[j].x + len + 1);
            j++;
        }
    }
    Num.erase(unique(Num.begin(), Num.end()), Num.end());
    vector<Data> V(Num.size());
    for(ll i = 1, p = 0, q = 0; i <= N; i++){
        while(p + 1 < Num.size() && !(Num[p] <= A[i].x && A[i].x < Num[p + 1])) p++;
        while(q + 1 < Num.size() && !(Num[q] <= A[i].x + len && A[i].x + len < Num[q + 1])) q++;
        Add[p]++; Del[q]++;
    }
    ll s = 1, e = 0;
    for(ll i = 0; i < V.size(); i++){
        e += Add[i];
        V[i].l = Num[i], V[i].r = (i + 1 == V.size() ? INF : Num[i + 1] - 1);
        for(ll j = 0; j < 3; j++) V[i].c[j] = F[j][s][e];
        s += Del[i];
    }
    deque<ll> dq[3];
    ll Res = 1e18;
    for(ll i = 0, j = 0; i < V.size(); i++){
        if(V[i].l + H - 1 >= V.back().l) break;
        for(ll k = 0; k < 3; k++){
            while(!dq[k].empty() && dq[k].front() < i) dq[k].pop_front();
        }
        while(j < V.size() && V[j].l <= V[i].l + H - 1){
            for(ll k = 0; k < 3; k++){
                while(!dq[k].empty() && V[dq[k].back()].c[k] <= V[j].c[k]) dq[k].pop_back();
                dq[k].push_back(j);
            }
            j++;
        }
        Res = min(Res, max(V[dq[0].front()].c[0] + V[dq[1].front()].c[1], V[dq[2].front()].c[2]));
    }
    return Res;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> H >> W >> N;
    vector<ll> Cand;
    for(ll i = 1; i <= N; i++){
        cin >> A[i].x >> A[i].y;
        Cand.push_back(A[i].x - 1);
        Cand.push_back(H - A[i].x);
    }
    sort(A + 1, A + N + 1);
    for(ll i = 1; i <= N; i++){
        set<ll> S;
        for(ll j = i; j <= N; j++){
            S.insert(A[j].y);
            F[0][i][j] = *S.begin() - 1, F[1][i][j] = W - *prev(S.end());
            for(auto it = S.begin(); ; it++){
                if(next(it) == S.end()) break;
                F[2][i][j] = max(F[2][i][j], *next(it) - *it - 1);
            }
        }
    }
    ll mn = H - A[N].x + A[1].x - 1;
    for(ll i = 2; i <= N; i++){
        mn = max(mn, A[i].x - A[i - 1].x - 1);
    }
    ll Ans = 1e18;
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= N; j++){
            Cand.push_back(A[j].x - A[i].x - 1);
            Cand.push_back(A[j].x - 1 + H - A[i].x);
        }
    }
    sort(Cand.begin(), Cand.end());
    Cand.erase(unique(Cand.begin(), Cand.end()), Cand.end());
    for(auto i : Cand){
        if(i < mn) continue;
        Ans = min(Ans, i + Solve(i));
    }
    cout << Ans;
}

Compilation message (stderr)

cultivation.cpp: In function 'll Solve(ll)':
cultivation.cpp:35:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         while(p + 1 < Num.size() && !(Num[p] <= A[i].x && A[i].x < Num[p + 1])) p++;
      |               ~~~~~~^~~~~~~~~~~~
cultivation.cpp:36:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(q + 1 < Num.size() && !(Num[q] <= A[i].x + len && A[i].x + len < Num[q + 1])) q++;
      |               ~~~~~~^~~~~~~~~~~~
cultivation.cpp:40:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(ll i = 0; i < V.size(); i++){
      |                   ~~^~~~~~~~~~
cultivation.cpp:42:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         V[i].l = Num[i], V[i].r = (i + 1 == V.size() ? INF : Num[i + 1] - 1);
      |                                    ~~~~~~^~~~~~~~~~~
cultivation.cpp:48:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(ll i = 0, j = 0; i < V.size(); i++){
      |                          ~~^~~~~~~~~~
cultivation.cpp:53:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(j < V.size() && V[j].l <= V[i].l + H - 1){
      |               ~~^~~~~~~~~~

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