Submission #447638

#	Time	Username	Problem	Language	Result	Execution time	Memory
447638		Haruto810198	Cultivation (JOI17_cultivation)	C++17	5 / 100	2079 ms	464 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = 1e18;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 310;

int n;
int R, C;
pii pt[MAX];

int res;

int check(int dxl, int dxr){

    //cerr<<"check("<<dxl<<", "<<dxr<<") : "<<endl;

    multiset<int> st;
    vector<vi> ev;
    /// insert : time,  1, pos
    /// erase  : time, -1, pos

    vector<vi> seg; /// minL, minR, minSum, L, R

    FOR(i, 1, n, 1){
        ev.pb({pt[i].F - dxl, 1, pt[i].S});
        ev.pb({pt[i].F + dxr + 1, -1, pt[i].S});
    }

    sort(ev.begin(), ev.end());

    int pv_time = -LNF;
    int minL = LNF, minR = LNF, minSum = LNF;

    for(auto E : ev){

        int Time = E[0];
        int type = E[1];
        int pos = E[2];

        if(pv_time < Time){
            seg.pb({minL, minR, minSum, pv_time, Time - 1});
        }

        pv_time = Time;

        if(type == 1){
            st.insert(pos);
        }
        else{
            auto it = st.find(pos);
            st.erase(it);
        }

        if(st.empty()){
            minSum = LNF;
        }
        else{

            minSum = 0;
            for(auto it=st.begin(); it!=st.end(); it++){

                if(it == st.begin()){
                    minL = *it - 1;
                }

                if(next(it) == st.end()){
                    minR = C - *it;
                }
                else{
                    auto nit = next(it);
                    minSum = max(minSum, *nit - *it - 1);
                }

            }

        }

    }

    int retL = 0, retR = 0, retSum = 0;

    //cerr<<"seg : "<<endl;

    bool AC = 0;

    for(auto I : seg){

        if(I[3] > R or I[4] < 1){
            continue;
        }
        /*
        cerr<<"{";
        for(auto i : I){
            cerr<<i<<", ";
        }
        cerr<<"}"<<endl;
        */
        retL = max(retL, I[0]);
        retR = max(retR, I[1]);
        retSum = max(retSum, I[2]);

        if(I[4] >= R){
            AC = 1;
        }

    }

    retSum = max(retSum, retL + retR);

    if(AC == 0){
        retSum = LNF;
    }

    //cerr<<dxl + dxr + retSum<<endl;

    return dxl + dxr + retSum;

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>R>>C;
    cin>>n;
    FOR(i, 1, n, 1){
        cin>>pt[i].F>>pt[i].S;
    }

    res = LNF;

    FOR(dxl, 0, R, 1){
        FOR(dxr, 0, R, 1){
            res = min(res, check(dxl, dxr));
        }
    }

    cout<<res<<'\n';

    return 0;

}

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