oj.uz

답안 #132204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132204 2019-07-18T13:10:44 Z shayan_p Cultivation (JOI17_cultivation) C++14
0 / 100
 3 ms 504 KB 
// 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] >= a[k] ) vv.PB({a[k], a[i]-a[j]-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);

	    vl=max(vl,nw);

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

	    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);
	    
	    while( ptb<n && a[ arr[ptb] ] + p.S <= nw)
		rem( b[ arr[ptb] ] ), ptb++;
	    nw=vl;
	}

	//	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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -