Submission #1200925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200925		PlayVoltz	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	193 ms	12160 KiB

bridge

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <fstream>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int tsum=0, bsum=0;
multiset<int> top, down;

bool custom(pii a, pii b){
	return a.fi+a.se<b.fi+b.se;
}

void add(int a){
	if (down.empty()||*(--down.end())>=a)down.insert(a), bsum+=a;
	else top.insert(a), tsum+=a;
	while (top.size()>=down.size())tsum-=*top.begin(), bsum+=*top.begin(), down.insert(*top.begin()), top.erase(top.begin());
	while (top.size()+1<down.size())bsum-=*(--down.end()), tsum+=*(--down.end()), top.insert(*(--down.end())), down.erase((--down.end()));
}

int32_t main(){
	int k, n, ans=0;
	cin>>k>>n;
	vector<pii> vect;
	for (int i=0, a, b; i<n; ++i){
		char c, d;
		cin>>c>>a>>d>>b;
		if (c==d)ans+=abs(a-b);
		else vect.pb(mp(a, b)), ++ans;
	}
	if (vect.empty()){
		cout<<ans;
		return 0;
	}
	sort(vect.begin(), vect.end(), custom);
	vector<int> pm(vect.size());
	for (int i=0; i<vect.size(); ++i)add(vect[i].fi), add(vect[i].se), pm[i]=tsum-bsum;
	if (k==1){
		cout<<ans+pm[vect.size()-1];
		return 0;
	}
	top.clear();
	down.clear();
	tsum=bsum=0;
	int mn=pm[vect.size()-1];
	for (int i=vect.size()-1; i>=1; --i)add(vect[i].fi), add(vect[i].se), mn=min(mn, pm[i-1]+tsum-bsum);
	cout<<ans+mn;
}

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