Submission #380481

#	Time	Username	Problem	Language	Result	Execution time	Memory
380481		Ccucumber12	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2092 ms	6584 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;

void solve() {
	int n, tp ;
	ll sum = 0 ;
	vec<pll> g ;
	
	cin >> tp >> n ;
	rep(i, n) {
		char c1, c2 ;
		ll a, b ;
		cin >> c1 >> a >> c2 >> b ;
		if(c1 == c2) {
			sum += abs(a - b) ;
		} else {
			++sum ;
			g.EB(a, b) ;
		}
	}
	int m = siz(g) ;
	
	ll ans = 0 ;
	if(tp == 1) {
		vec<int> v ;
		for(auto i:g) {
			v.EB(i.F) ;
			v.EB(i.S) ;
		}
		sort(ALL(v)) ;
		rep(i, 2*m) ans += abs(v[i] - v[m]) ;
	} else {
		sort(ALL(g), [](pll a, pll b) {
			return (a.F + a.S) < (b.F + b.S) ;
		});
		
		ans = LLINF ;
		vec<pll> v ;
		rep(i, m + 1) {
			ll ret = 0 ;
			vec<ll> tmp ;
			for(auto j:v) {
				tmp.EB(j.F);
				tmp.EB(j.S) ;
			}
			sort(ALL(tmp)) ;
			rep(j, siz(tmp)) ret += abs(tmp[j] - tmp[siz(tmp) / 2]) ;

			tmp.clear();
			for(auto j:g) {
				tmp.EB(j.F) ;
				tmp.EB(j.S) ;
			}
			sort(ALL(tmp)) ;
			rep(j, siz(tmp)) ret += abs(tmp[j] - tmp[siz(tmp) / 2]) ;

			amin(ans, ret) ;
			
			if(siz(g)) {
				v.EB(g.back());
				g.pop_back() ;
				
			}
		}
	}
	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

*/
 

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