제출 #380530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380530		Ccucumber12	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	541 ms	17760 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 ;

	vec<info> ipt(n) ;
	rep(i, n) {
		char c1, c2 ;
		ll a, b ;
		cin >> c1 >> a >> c2 >> b ;

		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) ;
	});
	map<int,int> lt, lb, rt;
	rep(i, m) lb[v[i]] ++ ;
	REP(i, m, 2*m - 1) lt[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[l] -- ;
			if(lt[l] == 0) lt.erase(l) ;
			ret -= l;
			++cnt ;
		} else {
			lb[l] -- ;
			if(lb[l] == 0) lb.erase(l) ;
			ret += l ;
		}

		if(lt.count(r)) {
			lt[r] -- ;
			if(lt[r] == 0) lt.erase(r) ;
			ret -= r;
			++cnt ;
		} else {
			lb[r] -- ;
			if(lb[r] == 0) lb.erase(r) ;
			ret += r ;
		}

		debug(i, l, r) ;

		if(cnt == 2) {
			int k = prev(lb.end()) -> F;
			lb[k] -- ;
			if(lb[k] == 0) lb.erase(k) ;
			lt[k] ++ ;
			ret += k * 2 ;
		} else if(cnt == 0) {
			int k = lt.begin() -> F;
			lt[k] -- ;
			if(lt[k] == 0) lt.erase(k) ;
			lb[k] ++ ;
			ret -= k * 2 ;
		}

		debug(ret) ;

		ret += l + r;
		rt[l] ++ ;
		rt[r] ++ ;

		int a = rt.begin() -> F;
		rt[a] -- ;
		if(rt[a] == 0) 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
 
2 30
b 766271216 a 937314442
a 779564772 b 207005877
b 95226585 a 37308850
b 949152497 a 416813552
b 230947976 a 333801978
b 461112874 b 783620166
a 114475360 b 766317225
a 263561391 b 530121282
b 111199740 b 354028532
b 570345272 b 420909041
b 856833680 b 20949817
a 77984478 b 137779210
a 620999255 b 20635990
a 845360953 a 507947117
b 851252842 b 763149666
b 257277712 b 150883515
a 345298754 b 344839460
a 245599534 a 310651023
a 123350138 b 326571661
a 751451706 a 607651642
a 662695013 b 585467271
b 146688392 a 749163292
b 626027972 b 896252720
b 288531657 a 36565110
b 965468565 b 874520258
a 521546287 b 63794524
a 557689007 b 881650300
a 877999069 a 861287861
b 360274512 b 643721912
a 209640343 b 812074221

*/
 
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: 37 / 37