Submission #1160558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160558		tod	Cultivation (JOI17_cultivation)	C++20	0 / 100	0 ms	392 KiB

cultivation

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

bool cmp(pair<ll,ll> x, pair<ll,ll>y){
    if(x.fi==y.fi) return x.se<y.se;
    return x.fi<y.fi;
}
pair<ll,ll> a[5005];
map<ll,ll> mp1,mp2;
vector<pair<ll,ll>> ans[10];
int main() {
    ll n,r,c,res=INT_MAX;
    cin>>r>>c;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i].fi>>a[i].se;
    }
    for(ll i=1;i<=n;i++){
        vector<ll> b;
        ll d,l;
        l=d=0;
        // c.push_back(0);
        // c=b;
        if(mp1[a[i].fi]==0){
            ll h1=0,h2=0;
            for(ll j=1;j<=n;j++){
                if(a[i].fi == a[j].fi){
                    b.push_back(a[j].se);
                }
            }
            // for(ll x:b) cout<<x<<' ';
            // b.push_back(c+1);
            sort(b.begin(),b.end());
            for(ll j=0;j<b.size()-1;j++){
                if(b[j+1] - b[j] -1 <= d) continue;
                d = b[j+1] - b[j] -1;
                // cout<<1;
            }
            h1 = b.back() - b[0] +1;
            if(c - b.back() >=  d){
                h1 += d;
            }
            else{
                h1 += c - b[b.size()-1];
            }
            if(c-(b[0]+h1-1) > b[0]-1 ) ans[1].push_back({c-h1 + d,a[i].fi});
            else ans[2].push_back({c-h1 + d,a[i].fi});
            // cout<<c<<' '<<h1<<' '<<d<<' '<<c-h1 + d<<endl;
            for(ll j=b.size()-1;j>0;j--){
                if(b[j] - b[j-1] -1 <= l) continue;
                l = b[j] - b[j-1] -1;
            }
            h2 = b[b.size()-1] - b[0] +1;
            if(b[0] -1 >=  l){
                h2 += l;
            }
            else{
                h2 += b[0] -1;
            }
            if(c-(b[0]+h2-1) > b[0]-1 ) ans[1].push_back({c-h2 + l,a[i].fi});
            else  ans[2].push_back({c-h2 + l,a[i].fi});
            // cout<<c-h2 + l<<endl;
            mp1[a[i].fi]++;
            
        }
        d=l=0;
        b.clear();
        if(mp2[a[i].se]==0){
            ll h1=0,h2=0;
            for(ll j=1;j<=n;j++){
                if(a[i].se == a[j].se){
                    b.push_back(a[j].fi);
                }
            }
            // b.push_back(c+1);
            sort(b.begin(),b.end());
            for(ll j=0;j<b.size()-1;j++){
                if(b[j+1] - b[j] -1 <= d) continue;
                d = b[j+1] - b[j] -1;
            }
            h1 = b[b.size()-1] - b[0] +1;
            if(r - b[b.size()-1] >=  d){
                h1 += d;
            }
            else{
                h1 += r - b[b.size()-1];
            }
            if(r-(b[0]+h1-1) > b[0]-1 ) ans[3].push_back({r-h1 + d,a[i].fi});
            else ans[4].push_back({r-h1 + d,a[i].fi});
            // cout<<c-h1 + d<<endl;
            for(ll j=b.size()-1;j>0;j--){
                if(b[j] - b[j-1] -1 <= l) continue;
                l = b[j] - b[j-1] -1;
            }
            h2 = b[b.size()-1] - b[0] +1;
            if(b[0] -1 >=  l){
                h2 += l;
            }
            else{
                h2 += b[0] -1;
            }
            if(r-(b[0]+h2-1) > b[0]-1 ) ans[1].push_back({r-h1 + d,a[i].fi});
            else ans[2].push_back({r-h1 + d,a[i].fi});
            // c.push_back(r+1);
            // cout<<c-h2 + l<<endl;
            mp2[a[i].se]++;
        }
        b.clear();
        
    }
    for(ll i=1;i<=4;i++){
        sort(ans[i].begin(),ans[i].end(),cmp);
        ll m=0,ans1=INT_MAX,d,l;
        d=l=0;
        vector<ll>b;
        while(m<ans[i].size() && ans[i][m].fi==ans[i][0].fi){
            b.push_back(ans[i][m].se);
            m++;
        }
        // cout<<m;
        // for(pair<ll,ll> x : ans[i]){
        //     cout<<x.se<<' ';
        // }
        // cout<<endl;
        if(m==0) continue;
          if(i <= 2){
            ll h1=0,h2=0;
            for(ll j=0;j<b.size()-1;j++){
                if(b[j+1] - b[j] -1 <= d) continue;
                d = b[j+1] - b[j] -1;
            }
            // cout<<d<<' ';
            h1 = b.back() - b[0] +1;
            if(r - b.back() >=  d){
                h1 += d;
            }
            else{
                h1 += r - b[b.size()-1];
            }
            
            ans1 = min(ans1,r-h1 + d);
            for(ll j=b.size()-1;j>0;j--){
                if(b[j] - b[j-1] -1 <= l) continue;
                l = b[j] - b[j-1] -1;
            }
            h2 = b[b.size()-1] - b[0] +1;
            if(b[0] -1 >=  l){
                h2 += l;
            }
            else{
                h2 += b[0] -1;
            }
            ans1 = min(ans1,r-h2 + l);
          }
          
          else{
          
            ll h1=0,h2=0;
            for(ll j=0;j<b.size()-1;j++){
                if(b[j+1] - b[j] -1 <= d) continue;
                d = b[j+1] - b[j] -1;
            }
            h1 = b.back() - b[0] +1;
            if(c - b.back() >=  d){
                h1 += d;
            }
            else{
                h1 += c - b[b.size()-1];
            }
            ans1 = min(ans1,c-h1 + d);
            for(ll j=b.size()-1;j>0;j--){
                if(b[j] - b[j-1] -1 <= l) continue;
                l = b[j] - b[j-1] -1;
            }
            h2 = b[b.size()-1] - b[0] +1;
            if(b[0] -1 >=  l){
                h2 += l;
            }
            else{
                h2 += b[0] -1;
            }
            ans1 = min(ans1,c-h2 + l);
          }
        
        // cout<<ans1<<' '<<ans[i][0].fi<<'\n';
        if(res>ans1 + ans[i][0].fi) res = ans1 + ans[i][0].fi ;
        
    }
    cout<<res;
    return 0;
}

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