Submission #380531

#	Time	Username	Problem	Language	Result	Execution time	Memory
380531		Ccucumber12	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2085 ms	15200 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
//#pragma gcc optimize("O3,unroll-loop")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
 
#define F first
#define S second
#define rs resize
#define EB emplace_back
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define siz(v) ((int)v.size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
 
#ifdef cc12
 
#define debug(...) cerr<<"#"<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__);
#define endl '\n'
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);
 
#else
 
#define debug(...)
#define kiyohime
 
#endif
 
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using Prior = priority_queue<T>;
template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>;
 
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const double PI  = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0,1,0,-1,1,1,-1,-1};
const int yy[8] = {1,0,-1,0,1,-1,-1,1};
 
unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(seed);
uniform_int_distribution<int> dist(1, 1e6);
 
template<typename T> void dbg(T x){ cerr<<x<<endl; }
template<typename T, typename ...A> void dbg(T x, A ...y){ cerr<<x<<", "; dbg(y...);}
template<typename T> void amax(T &a, T b) {if(a < b) a = b;}
template<typename T> void amin(T &a, T b) {if(a > b) a = b;}
template<typename T> bool INR(T a, T b, T c) {return b <= a && a <= c;}
void pmod(ll &a, ll b) {a = (a+b)%MOD;}
void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;}
void tmod(ll &a, ll b) {a = (a*b)%MOD;}
template<typename T> void UNI(vec<T> &v) {sort(ALL(v)); v.rs(unique(ALL(v))-v.begin());}
int gi() {int ret; cin >> ret; return ret;}
ll gl() {ll ret; cin >> ret; return ret;}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}
ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;}
 
const int MXN = 50;
const int N = MXN + 10;
 
struct info {
	char c1, c2;
	ll a, b ;
};
 
void solve() {
	ll n, tp, sum = 0 ;
	vec<pll> g ;
	
	cin >> tp >> n ;
	
//	tp = 2, n = 10 ;
	
	vec<info> ipt(n) ;
	rep(i, n) {
		char c1, c2 ;
		ll a, b ;
		cin >> c1 >> a >> c2 >> b ;
		
		// <random>
//		c1 = rng() & 1 ? 'a' : 'b' ;
//		c2 = rng() & 1 ? 'a' : 'b' ;
//		a = rng() % 10 ;
//		b = rng() % 10 ;
//
		// </random>
		
		ipt[i] = {c1, c2, a, b} ;
		if(c1 == c2) {
			sum += abs(a - b) ;
		} else {
			++sum ;
			g.EB(a, b) ;
		}
	}
	
	
	int m = siz(g) ;
	
	ll ret = 0 ;
	vec<ll> v ;
	for(auto i:g) {
		v.EB(i.F) ;
		v.EB(i.S) ;
	}
	sort(ALL(v)) ;
	rep(i, m) ret -= v[i]  ;
	REP(i, m, 2*m - 1) ret += v[i] ;
	
	if(tp == 1) {
		cout << ret + sum << endl;
		return ;
	}
	
	sort(ALL(g), [](pll a, pll b) {
		return (a.F + a.S) < (b.F + b.S) ;
	});
	multiset<ll> lt, lb, rt;
	rep(i, m) lb.insert(v[i]) ;
	REP(i, m, 2*m - 1) lt.insert(v[i]) ;
	
	ll ans = ret ;
	debug(ret) ;
	rep(i, m) {
		ll l = g[i].F, r = g[i].S, cnt = 0 ;
		if(lt.count(l)) {
			lt.erase(lt.find(l)) ;
			ret -= l;
			++cnt ;
		} else {
			ret += l ;
			lb.erase(lb.find(l)) ;
		}
		
		if(lt.count(r)) {
			lt.erase(lt.find(r)) ;
			ret -= r;
			++cnt ;
		} else {
			ret += r ;
			lb.erase(lb.find(r)) ;
		}
		
		debug(i, l, r) ;
		
		if(cnt == 2) {
			auto k = prev(lb.end()) ;
			lb.erase(k);
			lt.insert(*k) ;
			ret += *k * 2 ;
		} else if(cnt == 0) {
			auto k = lt.begin() ;
			lt.erase(k) ;
			lb.insert(*k) ;
			ret -= *k * 2 ;
		}
		
		debug(ret) ;
		
		ret += l + r;
		rt.insert(l) ;
		rt.insert(r) ;
		
		auto a = rt.begin() ;
		rt.erase(a) ;
		ret -= *a * 2 ;
		
		debug(ret) ;
		
		amin(ans, ret) ;
	}
	cout << ans + sum << endl ;
	
}
 
/*
 
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
 
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
 
2 10
a 9 a 5
b 3 a 5
b 6 a 3
b 9 a 8
a 8 b 8
a 4 b 5
a 2 a 7
a 6 a 5
b 0 a 6
a 3 a 5
 
*/
 
int32_t main(){
    kiyohime
    int T = 1;
 
//    cin >> T;
    rep1(i, T) {
//		cout << "Case #" << i << endl ;
        solve();
//		cout << endl ;
    }
}
 
//  _____                       _           ___   ___
// |     |___ _ _ ___ _ _ _____| |_ ___ ___|_  | |_  |
// |   --|  _| | |  _| | |     | . | -_|  _|_| |_|  _|
// |_____|___|___|___|___|_|_|_|___|___|_| |_____|___|

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