Submission #916706

#TimeUsernameProblemLanguageResultExecution timeMemory
916706huantranPalembang Bridges (APIO15_bridge)C++17
0 / 100
2 ms348 KiB
#include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <queue> using namespace std; typedef long long int ll; const int maxn = 1e6 + 5; const int INF = 1e9; const ll inf = 1e18; ll k, n; vector<pair<ll, ll>> pos; ll pre[maxn], suf[maxn]; priority_queue<ll> ql; priority_queue<ll, vector<ll>, greater<ll>> qr; ll suml = 0, sumr = 0; void insert_queue(ll x) { ll med; if(ql.size()) med = ql.top(); else med = inf; if(x <= med) ql.push(x), suml += x; else qr.push(x), sumr += x; if(ql.size() > qr.size() + 1) { ll t = ql.top(); ql.pop(), suml -= t; qr.push(t), sumr += t; } else if(qr.size() > ql.size()) { ll t = qr.top(); qr.pop(), sumr -= t; ql.push(t), suml += t; } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> n; ll tol_dis = 0; for(int i = 1; i <= n; i++) { char a, b; ll x, y; cin >> a >> x >> b >> y; if(x > y) swap(x, y); if(a == b) tol_dis += (y - x); else pos.push_back({x, y}); } tol_dis += (int)pos.size(); sort(pos.begin(), pos.end(), [&](const pair<ll, ll> &a, const pair<ll, ll> &b){ if((a.first + a.second) == (b.first + b.second)) return a < b; return (a.first + a.second) < (b.first + b.second); }); for(int i = 0; i < (int)pos.size(); i++) { insert_queue(pos[i].first); insert_queue(pos[i].second); pre[i] = sumr - suml; } while(!ql.empty()) ql.pop(); while(!qr.empty()) qr.pop(); sumr = suml = 0; for(int i = (int)pos.size() - 1; i >= 0; i--) { insert_queue(pos[i].first); insert_queue(pos[i].second); suf[i] = sumr - suml; } ll ans = pre[(int)pos.size() - 1]; if(k == 2) { for(int i = 0; i < (int)pos.size(); i++) ans = min(ans, pre[i] + suf[i + 1]); } cout << ans + tol_dis; // for(int i = 0; i < (int)pos.size(); i++) // cout << pre[i] << ' '; // for(int i = 0; i < (int)pos.size(); i++) // { // cout << pos[i].first << ' ' << pos[i].second << '\n'; // } }

Compilation message (stderr)

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