Submission #132216

#	Time	Username	Problem	Language	Result	Execution time	Memory
132216		shayan_p	Cultivation (JOI17_cultivation)	C++14	0 / 100	3 ms	504 KiB

cultivation

// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=310,mod=1e9+7;
const ll inf=1e18;

int arr[maxn], a[maxn], b[maxn];

map<int,int> pos, cnt;

void add(int x){
    //    cout<<"SALAM "<<x<<endl;
    if(pos.count(x)){
	pos[x]++;
	return;
    }
    auto it=pos.lower_bound(x);

    if( it != pos.begin() && it != pos.end() ){
	int ln= (it->S) - (prev(it)->S) -1;
	if(--cnt[ln] == 0) cnt.erase(ln);
    }
    if( it != pos.begin() ){
	int ln= x - (prev(it)->S) - 1;
	cnt[ln]++;
    }
    if( it != pos.end() ){
	int ln= (it->S) - x - 1;
	cnt[ln]++;
    }
    pos[x]++;
}
void rem(int x){
    //    cout<<"DELETE "<<x<<endl;
    if(--pos[x] != 0) return;
    pos.erase(x);

    auto it=pos.lower_bound(x);

    if(it != pos.end() ){
	int ln= (it->S) - x - 1;
	if( --cnt[ln] == 0 ) cnt.erase(ln);
    }
    if(it != pos.begin() ){
	int ln= x - (prev(it)->S) - 1;
	if( --cnt[ln] == 0 ) cnt.erase(ln);
    }
    if(it != pos.begin() && it != pos.end() ){
	int ln= (it->S) - (prev(it)->S) - 1;
	cnt[ln]++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int N,M,n; cin>>N>>M>>n;

    vector<pii> vv;
    
    for(int i=0;i<n;i++){
	cin>>a[i]>>b[i];
	a[i]--, b[i]--;
	arr[i]=i;
    }

    sort(arr,arr+n,[](int i,int j){ return a[i]<a[j]; } );
    
    for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	    vv.PB({a[i],n-1-a[j]});
	}
    }
    for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	    if(a[i]>a[j]) continue;
	    for(int k=0;k<n;k++){
		if(a[i] - a[j] -1 >= a[k] ) vv.PB({a[k], a[i]-a[j]-1-a[k]});
	    }
	}
    }

    sort(vv.begin(), vv.end() );
    vv.resize( unique(vv.begin(), vv.end() ) - vv.begin() );

    ll ans= ll(N) + ll(M);
    
    for(pii p:vv){

	int pta=0, ptb=0, nw=0, mxd=0, mxa=0, mxb=0;
	
	pos.clear(), cnt.clear();
	
	while(pta<n || ptb<n){
	    int vl=1e9;
	    if(pta<n) vl=min(vl, a[ arr[pta] ] - p.F);
	    if(ptb<n) vl=min(vl, a[ arr[ptb] ] + p.S +1);

	    nw=max(vl,nw);

	    if(nw>=N) break;
			 
	    while( pta<n && a[ arr[pta] ] - p.F <= nw)
		add( b[ arr[pta] ] ), pta++;

	    while( ptb<n && a[ arr[ptb] ] + p.S +1 <= nw)
		rem( b[ arr[ptb] ] ), ptb++;

	    if( pos.empty() ) goto Hell;
	    
	    mxa= max(mxa, pos.begin()->F);
	    mxb= max(mxb, M-1- (pos.rbegin()->F) );
	    mxd= max(mxd, cnt.rbegin()->F);
	}

	//	cout<<"HEYY "<<p.F<<" "<<p.S<<" "<<mxa<<" "<<mxb<<" "<<mxd<<endl;
	
	ans= min(ans, ll(p.F) + ll(p.S) + ll( max( mxa + mxb, mxd ) ) );
	Hell:;
    }
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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