Submission #17410

#	Time	Username	Problem	Language	Result	Execution time	Memory
17410		comet	Palembang Bridges (APIO15_bridge)	C++98	0 / 100	0 ms	4300 KiB

bridge

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

struct pt{
	ll x,y;
	bool operator<(const pt& r)const{
		return x+y<r.x+r.y;
	}
};

int K,N,sz;
ll base,ans,sum;
ll L[100010],R[100010];
pt a[100010];

priority_queue<ll> lo;
priority_queue<ll,vector<ll>,greater<ll> > hi;

void push(int x){
	lo.push(x);
	ll t;
	while(!hi.empty()&&!lo.empty()&&hi.top()<=lo.top()){
		t=lo.top();lo.pop();
		hi.push(t);
		t=hi.top();hi.pop();
		lo.push(t);
	}
	while(hi.size()+1<lo.size()){
		t=lo.top();lo.pop();
		hi.push(t);
	}
}

void f(ll s[]){
	for(int i=0;i<sz;i++){
		push(a[i].x);
		push(a[i].y);
		int mid=(lo.top()+hi.top())/2;
		for(int j=0;j<=i;j++){
			s[i]+=abs(a[j].x-mid);
			s[i]+=abs(a[j].y-mid);
		}
	}
}

int main(){
	//freopen("bridge.in","r",stdin);

	scanf("%d%d ",&K,&N);
	char tx,ty;
	ll x,y;
	for(int i=0;i<N;i++){
		scanf("%c %lld %c %lld ",&tx,&x,&ty,&y);
		if(tx==ty){
			base+=y-x-1;
		}else{
			a[sz++]=pt{x,y};
		}
	}
	base+=N;

	sort(a,a+sz);

	f(L);
	if(K==1){
		printf("%lld",L[sz-1]+base);
		return 0;
	}
	reverse(a,a+sz);
	f(R);

	ans=-1e18;
	for(int i=0;i<sz;i++){
		ans=max(ans,L[i]+R[sz-1-i]);
	}
	printf("%lld",ans+base);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:60:14: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
    a[sz++]=pt{x,y};
              ^
bridge.cpp:52:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d ",&K,&N);
                      ^
bridge.cpp:56:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %lld %c %lld ",&tx,&x,&ty,&y);
                                          ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37