Submission #1175865

#TimeUsernameProblemLanguageResultExecution timeMemory
1175865CodeLakVNPalembang Bridges (APIO15_bridge)C++17
100 / 100
88 ms3520 KiB
#include <bits/stdc++.h> using namespace std; #define task "15_bridge" #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define ll long long #define F first #define S second template<class X, class Y> bool minimize(X &x, Y y) { if (x > y) { x = y; return true; } return false; } typedef pair<int, int> ii; int k, numCitizen; vector<ii> citizen; ll ans = 0; namespace sub12 { vector<int> pos; void solve() { int n = (int)citizen.size(); if (n == 0) { cout << ans << "\n"; return; } FOR(i, 0, n - 1) { pos.push_back(citizen[i].F); pos.push_back(citizen[i].S); } sort(pos.begin(), pos.end()); n = pos.size(); int x = pos[n / 2]; ll res = 0; for (ii p : citizen) { res += 1LL * abs(x - p.F) + 1LL * abs(x - p.S); } cout << ans + res << "\n"; } } namespace sub3 { vector<int> pos; void solve() { int n = (int)citizen.size(); if (n == 0) { cout << ans << "\n"; return; } FOR(i, 0, n - 1) { pos.push_back(citizen[i].F); pos.push_back(citizen[i].S); } sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end()); ll res = LLONG_MAX; for (int x : pos) { for (int y : pos) { if (x == y) continue; ll cur = 0; for (ii p : citizen) { cur += min(abs(x - p.F) + abs(x - p.S), abs(y - p.F) + abs(y - p.S)); } minimize(res, cur); } } if (res == LLONG_MAX) res = 0; cout << ans + res << "\n"; } } namespace sub45 { bool cmp(ii &A, ii &B) { return A.F + A.S < B.F + B.S; } priority_queue<int> leftPQ; priority_queue<int, vector<int>, greater<int>> rightPQ; ll leftSum = 0, rightSum = 0; void insert(int x) { int median = ((int)leftPQ.size() ? leftPQ.top() : 1000000001); if (x < median) { leftPQ.push(x); leftSum += x; } else { rightPQ.push(x); rightSum += x; } if ((int)leftPQ.size() > (int)rightPQ.size() + 1) { int val = leftPQ.top(); leftPQ.pop(); rightPQ.push(val); leftSum -= val; rightSum += val; } else if ((int)rightPQ.size() > (int)leftPQ.size()) { int val = rightPQ.top(); rightPQ.pop(); leftPQ.push(val); rightSum -= val; leftSum += val; } } ll pre[100005]; void solve() { if ((int)citizen.size() == 0) { cout << ans << "\n"; return; } sort(citizen.begin(), citizen.end(), cmp); int n = (int)citizen.size(); FOR(i, 0, n - 1) { insert(citizen[i].F); insert(citizen[i].S); pre[i + 1] = rightSum - leftSum; } ll res = LLONG_MAX; while ((int)leftPQ.size()) leftPQ.pop(); while ((int)rightPQ.size()) rightPQ.pop(); leftSum = rightSum = 0; FOD(i, n - 1, 0) { insert(citizen[i].F); insert(citizen[i].S); minimize(res, rightSum - leftSum + pre[i]); } cout << ans + res << "\n"; } } int main() { if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> numCitizen; FOR(i, 1, numCitizen) { char a, b; int x, y; cin >> a >> x >> b >> y; if (a == b) ans += 1LL * abs(x - y); else { ans++; citizen.push_back({x, y}); } } if (k == 1) sub12::solve(); else if (k == 2 && numCitizen <= 100) sub3::solve(); else sub45::solve(); return 0; }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(task".out", "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...