oj.uz

Submission #380530

# Submission time Handle Problem Language Result Execution time Memory
380530 2021-03-22T08:06:12 Z Ccucumber12 Palembang Bridges (APIO15_bridge) C++14
100 / 100
 541 ms 17760 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 59 ms 7516 KB Output is correct
13 Correct 118 ms 7644 KB Output is correct
14 Correct 77 ms 7132 KB Output is correct
15 Correct 71 ms 4448 KB Output is correct
16 Correct 88 ms 7676 KB Output is correct
17 Correct 107 ms 7564 KB Output is correct
18 Correct 102 ms 7636 KB Output is correct
19 Correct 121 ms 7644 KB Output is correct
20 Correct 94 ms 7668 KB Output is correct
21 Correct 108 ms 7644 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 3 ms 492 KB Output is correct
21 Correct 3 ms 492 KB Output is correct
22 Correct 3 ms 492 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 3 ms 492 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 3 ms 364 KB Output is correct
20 Correct 3 ms 492 KB Output is correct
21 Correct 4 ms 492 KB Output is correct
22 Correct 3 ms 492 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 67 ms 7652 KB Output is correct
26 Correct 101 ms 8284 KB Output is correct
27 Correct 481 ms 16096 KB Output is correct
28 Correct 541 ms 17632 KB Output is correct
29 Correct 503 ms 17760 KB Output is correct
30 Correct 201 ms 9444 KB Output is correct
31 Correct 100 ms 9052 KB Output is correct
32 Correct 279 ms 17632 KB Output is correct
33 Correct 258 ms 17248 KB Output is correct
34 Correct 292 ms 17120 KB Output is correct
35 Correct 103 ms 9180 KB Output is correct
36 Correct 301 ms 17248 KB Output is correct
37 Correct 64 ms 8156 KB Output is correct