제출 #1312553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312553		thuhienne	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	155 ms	12176 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);
#define left __left__
#define right __right__

const int maxn = 100009;

int k,n,cnt;
ll offset = 0;
pair <int,int> segment[maxn];

ll sumleft,sumright;
multiset <int> left,right;

ll cost1[maxn],cost2[maxn];

void rebalance() {
	int len = left.size() + right.size();
	
	while (left.size() < (len + 1) / 2) {
		sumleft += *right.begin();
		left.insert(*right.begin());
		
		sumright -= *right.begin();
		right.erase(right.begin());
	}
	while (left.size() > (len + 1) / 2) {
		sumright += *left.rbegin();
		right.insert(*left.rbegin());
		
		auto x = left.end();x --;
		
		sumleft -= *x;
		left.erase(x);
	}
}
void add(int val) {
	if (right.size() && *right.begin() <= val) {
		right.insert(val);
		sumright += val;
	}
	else {
		left.insert(val);
		sumleft += val;
	}
	rebalance();
}
ll getcost() {
	int median = *left.rbegin();
	
	ll ret = 0;
	
	ret += 1ll * median * left.size() - sumleft;
	ret += sumright - 1ll * median * right.size();
	
	return ret;
}

void solve() {
	sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) {
		return a.first + a.second < b.first + b.second;
	});
	
	for (int i = 1;i <= n;i++) {
		add(segment[i].first);
		add(segment[i].second);
		cost1[i] = getcost();
	}
	
	left.clear(),right.clear();
	sumleft = sumright = 0;
	
	for (int i = n;i >= 1;i--) {
		add(segment[i].first);
		add(segment[i].second);
		cost2[i] = getcost();
	}
	
	ll res = cost1[n];
	if (k == 2) {
		for (int i = 1;i < n;i++) res = min(res,cost1[i] + cost2[i + 1]);
	}
	
	cout << res + offset;
	
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin >> k >> n;
    for (int i = 1;i <= n;i++) {
        char _1,_2;int __1,__2;
        cin >> _1 >> __1 >> _2 >> __2;
        if (_1 == _2) offset += abs(__2 - __1);
        else {
            segment[++cnt] = {__1,__2};
            offset++;
            if (segment[cnt].first > segment[cnt].second) swap(segment[cnt].first,segment[cnt].second);
        }
    }
    n = cnt;
    if (n == 0) {
    	cout << offset;
    	re;
	}
	
	solve();
	
}

/*
Aiming:
                                                           ==
                                                         +++++***
                                                        +:::::-=*
                                                         ------=
         ==========           ==================         --:--==              ============--
         ==========           ==-------=--:=--====       ---==++           ===========--====-=
        ==--========          ==--=================      =:::-=+          ==============----====
        ==:-=========         ===:===       =======      =::--=+         ========        ==--====
       ==--==========         ==-:===        =======     -:::-:=        =======           =======
      ==--:==  =======        ==--===        =======     =-:::-=        =======            =======
      =-.-===   =======       ==-====       =======     *:::----*       =======            =======
     ==--:==    =======       ==-==================     +-:::::-+       ======             =======
    ==-:-===     =======      ==--================     *=-:::::-=       =======            =======
    ==---===============      ==--=============        +--::---==*      ====--=            =======
   ===--=================     ==:-===                  =:-::::--=+      ====-===          =======
   ==.-===================    ==--===                  =::::::---+       ====---==      =========
  ==---==          =======    =======                 +-:---=====+        ==-===--==============
 =======            =======   =======                 =-:::::::--=+         =--=-=============
========             =======  =======                 =--::::::--=+           =============
                                                   ***++++++++++*****
*/

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