제출 #631437

#제출 시각아이디문제언어결과실행 시간메모리
631437BhavayGoyalPalembang Bridges (APIO15_bridge)C++14
0 / 100
1 ms212 KiB
#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; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ld long double #define ar array #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define f first #define s second #define endl "\n" const int MOD = 1e9+7; const int inf = 1e18; const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; // -------------------------------------------------- Main Code -------------------------------------------------- int a = 0, b = 0; multiset<int> leftt, rightt; void add(int x) { if (leftt.empty() || x < *leftt.rbegin()) { leftt.insert(x); a += x; if ((leftt.size()+rightt.size())%2 == 0 && leftt.size() > rightt.size()) { a -= *leftt.rbegin(); b += *leftt.rbegin(); rightt.insert(*leftt.rbegin()); leftt.erase(leftt.find(*leftt.rbegin())); } } else { rightt.insert(x); b += x; if (rightt.size() > leftt.size()) { a += *rightt.begin(); b -= *rightt.begin(); leftt.insert(*rightt.begin()); rightt.erase(rightt.begin()); } } } void sol() { int k, n; cin >> k >> n; vector<array<int, 2>> arr; int sameSide = 0; for (int i = 0; i < n; i++) { char a, b; int x, y; cin >> a >> x >> b >> y; if (a == b) sameSide += abs(x-y); else arr.pb({x, y}); } n = arr.size(); sameSide += n; sort(all(arr), [&](array<int, 2> a, array<int, 2> b) {return a[0]+a[1] < b[0]+b[1];}); vi pref(n+5); for (int i = 0; i < n; i++) { add(arr[i][0]); add(arr[i][1]); int median = *leftt.rbegin(); pref[i] = median*leftt.size() - a + b - median*rightt.size(); } if (k == 1) {cout << pref[n-1]+sameSide << endl;return;} leftt.clear(); rightt.clear(); a = 0, b = 0; vi suff(n); for (int i = n-1; i >= 0; i--) { add(arr[i][0]); add(arr[i][1]); int median = *leftt.rbegin(); suff[i] = median*leftt.size() - a + b - median*rightt.size(); } int ans = pref[n-1]; for (int i = 0; i < n-1; i++) ans = min(ans, pref[i]+suff[i+1]); cout << sameSide+ans << endl; } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...