Submission #447648

#	Time	Username	Problem	Language	Result	Execution time	Memory
447648		Haruto810198	Cultivation (JOI17_cultivation)	C++17	30 / 100	2061 ms	584 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;
    multiset<int> sums;

    for(auto E : ev){

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

        if(pv_time < Time){
            if(!sums.empty()){
                seg.pb({minL, minR, *prev(sums.end()), pv_time, Time - 1});
            }
            else{
                seg.pb({minL, minR, 0, pv_time, Time - 1});
            }
        }

        pv_time = Time;

        if(type == 1){

            st.insert(pos);

            auto it = st.find(pos);
            auto pit = prev(it);
            auto nit = next(it);

            if(it != st.begin() and it != prev(st.end()) ){
                sums.erase( sums.find(*nit - *pit - 1) );
                sums.insert(*nit - *it - 1);
                sums.insert(*it - *pit - 1);
            }
            else if(it == st.begin() and it != prev(st.end()) ){
                sums.insert(*nit - *it - 1);
            }
            else if(it != st.begin() and it == prev(st.end()) ){
                sums.insert(*it - *pit - 1);
            }

        }
        else{

            auto it = st.find(pos);
            auto pit = prev(it);
            auto nit = next(it);

            if(it != st.begin() and it != prev(st.end()) ){
                sums.insert(*nit - *pit - 1);
                sums.erase( sums.find(*nit - *it - 1) );
                sums.erase( sums.find(*it - *pit - 1) );
            }
            else if(it == st.begin() and it != prev(st.end()) ){
                sums.erase( sums.find(*nit - *it - 1) );
            }
            else if(it != st.begin() and it == prev(st.end()) ){
                sums.erase( sums.find(*it - *pit - 1) );
            }

            st.erase(it);

        }

        if(st.empty()){
            minL = LNF;
            minR = LNF;
        }
        else{
            minL = *st.begin() - 1;
            minR = C - *prev(st.end());
        }

        /*
        cerr<<"st : ";
        for(int i : st){
            cerr<<i<<" ";
        }
        cerr<<endl;

        cerr<<"sums : ";
        for(int i : sums){
            cerr<<i<<" ";
        }
        cerr<<endl;
        */

    }

    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: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20