제출 #410968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410968		CSQ31	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	132 ms	4548 KiB

bridge

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
priority_queue<int>lf;
priority_queue<int,vector<int>,greater<int>>rg;
ll slf = 0,srg = 0;
void insert(int x){
	int mid = lf.empty()?1000000001:lf.top();
	if(x >= mid){rg.push(x);srg+=x;}
	else {lf.push(x);slf+=x;}
	if(sz(lf) > sz(rg)+1){
		ll tmp = lf.top();
		lf.pop();
		rg.push(tmp);
		slf-=tmp;
		srg+=tmp;
	}
	else if(sz(rg) > sz(lf)){
		ll tmp = rg.top();
		rg.pop();
		lf.push(tmp);
		slf+=tmp;
		srg-=tmp;
		
	}
	
}
int main()
{
	owo
	int k,n;
	cin>>k>>n;
	vector<int>s,t;
	ll ans = 0;
	for(int i=0;i<n;i++){
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		if(a == c){ans+=abs(d-b);continue;}
		s.pb(b);
		t.pb(d);
	}
	if(k == 1){
		vector<int>p;
		for(int x:s)p.pb(x);
		for(int x:t)p.pb(x);
		if(!p.empty()){
		sort(all(p));
		   int mid = p[sz(p)/2];
		   for(int i=0;i<sz(p)/2;i++)ans+=mid-p[i];
		   for(int i=sz(p)/2;i<sz(p);i++)ans+=p[i]-mid;
	    }
	    cout<<ans+sz(p)/2;
	}
	else{
		n = sz(s);
		ll add  =0;
		if(n){
		vector<ll>pref(n),suff(n);
		vector<int>id(n);
		for(int i=0;i<n;i++)id[i] = i;
		sort(all(id),[&](int x,int y){return s[y]+t[y] > s[x]+t[x];});
		for(int i=0;i<n;i++){
			insert(s[id[i]]);
			insert(t[id[i]]);
			pref[i] = srg-slf;
		}
		
		slf = srg = 0;
		while(!lf.empty())lf.pop();
		while(!rg.empty())rg.pop();
		for(int i=n-1;i>=0;i--){
			insert(s[id[i]]);
			insert(t[id[i]]);
			suff[i] = srg-slf;
		}
		add = min(pref[n-1],suff[0]);
		for(int i=0;i<n-1;i++)add = min(add,pref[i]+suff[i+1]);
	}
		cout<<ans+add+n<<'\n';
	}
}

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