Submission #1258643

#TimeUsernameProblemLanguageResultExecution timeMemory
1258643gojo1107Palembang Bridges (APIO15_bridge)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fr(i,a,b) for (int i=a; i<b; i++) #define loop(x,n) for (int x=0; x<n; x++) #define mod 1000000007 #define inf (1LL<<60) #define all(x) (x).begin(), (x).end() typedef long double lld; typedef unsigned long long ull; #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" "; _print(x); cerr << endl; #else #define debug(x) #endif void _print(long long t) {cerr << t;} void _print(int t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(lld t) {cerr << t;} void _print(double t) {cerr << t;} void _print(ull t) {cerr << t;} template <class T, class V> void _print(pair <T, V> p); template <class T> void _print(vector <T> v); template <class T> void _print(set <T> v); template <class T, class V> void _print(map <T, V> v); template <class T> void _print(multiset <T> v); template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";} template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} bool cmp (pair<int,int> a, pair<int,int> b) { return a.first + a.second < b.first + b.second; } class SlidingMedian { priority_queue<int> left_max; // <= median priority_queue<int, vector<int>, greater<int>> right_min; // >= median long long sum_left = 0, sum_right = 0; void balance() { if (left_max.size() > right_min.size() + 1) { int val = left_max.top(); left_max.pop(); sum_left -= val; right_min.push(val); sum_right += val; } else if (right_min.size() > left_max.size()) { int val = right_min.top(); right_min.pop(); sum_right -= val; left_max.push(val); sum_left += val; } } public: void add(int num) { if (left_max.empty() || num <= left_max.top()) { left_max.push(num); sum_left += num; } else { right_min.push(num); sum_right += num; } balance(); } // Use LOWER median always (assumes left.size() >= right.size()) int median() const { return left_max.top(); } long long cost() const { long long m = median(); // sum |a - m| = m*L - sum_left + sum_right - m*R return m * 1LL * left_max.size() - sum_left + sum_right - m * 1LL * right_min.size(); } }; void solve() { int k, n; cin >> k >> n; long long ans = 0; vector<pair<int,int>> a; a.reserve(n); for (int i = 0; i < n; i++) { char ch1, ch2; int p, s; cin >> ch1 >> p >> ch2 >> s; if (ch1 == ch2) { ans += llabs(1LL * s - p); } else { a.pb({p, s}); } } if (a.empty()) { // nothing to pair/split cout << ans << '\n'; return; } sort(all(a), cmp); SlidingMedian s1, s2; int m = (int)a.size(); vector<long long> pre(m), suf(m); for (int i = 0; i < m; i++) { s1.add(a[i].first); s1.add(a[i].second); pre[i] = s1.cost(); } debug(pre); for (int i = m - 1; i >= 0; i--) { s2.add(a[i].first); s2.add(a[i].second); suf[i] = s2.cost(); } debug(suf); long long res = LLONG_MAX; for (int i = 0; i < m ; i++) { res = min(res, pre[i] + suf[i ]); } cout << (res + ans) << '\n'; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); freopen("Error.txt", "w", stderr); #endif fast_io; cout.setf(std::ios::fixed); cout<<setprecision(10); int t = 1; // cin >> t; while (t--) solve(); }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:141:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:142:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:143:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     freopen("Error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...