Submission #366142

#	Time	Username	Problem	Language	Result	Execution time	Memory
366142		YJU	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	364 KiB

bridge

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

priority_queue<ll> pqa;
priority_queue<ll,vector<ll>,greater<ll> > pqb;

ll k,n,sum,x,y,ans,suf[N],pre[N];
char A,B;
vector<pll> v;


void add(ll d){
	if(SZ(pqa)&&d<pqa.top())sum-=d,pqa.push(d);
	else sum+=d,pqb.push(d);
	while(SZ(pqa)>SZ(pqb)){
		d=pqa.top();pqa.pop();pqb.push(d);
		sum+=d*2;
	}
	while(SZ(pqb)>SZ(pqa)+1){
		d=pqb.top();pqb.pop();pqa.push(d);
		sum-=d*2;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>k>>n;
	REP1(i,n){
		cin>>A>>x>>B>>y;
		if(A==B){ans+=y-x;continue;}
		++ans;
		v.pb(mp(x+y,y));
	}
	sort(v.begin(),v.end());
	n=SZ(v);
	if(n==0){cout<<ans<<"\n";return 0;}
	while(SZ(pqa))pqa.pop();
	while(SZ(pqb))pqb.pop();
	sum=0;
	REP(i,n){
		add(v[i].X-v[i].Y);
		add(v[i].Y);
		//cout<<sum<<" "<<pqb.top()<<" "<<SZ(pqa)-SZ(pqb)<<"\n";
		pre[i]=sum;
	}
	while(SZ(pqa))pqa.pop();
	while(SZ(pqb))pqb.pop();
	sum=0;
	for(int i=n-1;i>=0;i--){
		add(v[i].X-v[i].Y);
		add(v[i].Y);
		suf[i]=sum;
	}
	//cout<<pre[n-1]<<"\n";
	ll tans=ans+pre[n-1];
	if(k==2){
		for(int i=0;i+1<n;i++)tans=min(tans,ans+pre[i]+suf[i+1]);
	}
	cout<<tans<<"\n";
	return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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