Submission #870956

#TimeUsernameProblemLanguageResultExecution timeMemory
870956anha3k25cvpSchools (IZhO13_school)C++14
100 / 100
85 ms16144 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 5 + 1e5; const int inf = 7 + 1e9; struct Node { ll a, b; bool operator <(const Node &O) const { return a > O.a; } }; int main() { #define TASKNAME "" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen (TASKNAME".inp", "r", stdin); freopen (TASKNAME".out", "w", stdout); } int n, m, s; cin >> n >> m >> s; vector <Node> e(n + 1); for (int i = 1; i <= n; i ++) cin >> e[i].a >> e[i].b; sort(e.begin() + 1, e.end()); vector <int> inqueue(n + 1, 0); priority_queue <II> a1, a2; ll ans = 0; for (int i = 1; i <= m; i ++) { ans += e[i].a; inqueue[i] = 1; a1.push({-e[i].a, i}); a2.push({e[i].b - e[i].a, i}); } priority_queue <II> b1, b2; for (int i = m + 1; i <= m + s; i ++) { while (!a1.empty() && inqueue[a1.top().nd] != 1) a1.pop(); while (!a2.empty() && inqueue[a2.top().nd] != 1) a2.pop(); if (!a2.empty() && e[i].b - e[i].a < a2.top().st) { int u = a2.top().nd; ans += e[i].a + e[u].b - e[u].a; inqueue[u] = 2; inqueue[i] = 1; a1.push({-e[i].a, i}); a2.push({e[i].b - e[i].a, i}); b1.push({e[u].a - e[u].b, u}); b2.push({-e[u].b, u}); } else { ans += e[i].b; inqueue[i] = 2; b1.push({e[i].a - e[i].b, i}); b2.push({-e[i].b, i}); } } if (s > 0) { for (int i = m + s + 1; i <= n; i ++) { while (!a1.empty() && inqueue[a1.top().nd] != 1) a1.pop(); while (!a2.empty() && inqueue[a2.top().nd] != 1) a2.pop(); while (!b1.empty() && inqueue[b1.top().nd] != 2) b1.pop(); while (!b2.empty() && inqueue[b2.top().nd] != 2) b2.pop(); ll delta1 = 0, delta2 = 0, delta3 = 0; if (!a1.empty() && e[i].b + a1.top().st > -b1.top().st) { int u = a1.top().nd, v = b1.top().nd; delta1 = e[i].b + e[v].a - e[v].b - e[u].a; } if (e[i].b > -b2.top().st) { int v = b2.top().nd; delta2 = e[i].b - e[v].b; } if (!a2.empty() && -b2.top().st - e[i].a < a2.top().st) { int u = a2.top().nd, v = b2.top().nd; delta3 = e[u].b + e[i].a - e[v].b - e[u].a; } ll ma = max({delta1, delta2, delta3}); ans += ma; if (ma == 0) continue; if (delta1 == ma) { int u = a1.top().nd, v = b1.top().nd; inqueue[u] = 0; inqueue[v] = 1; a1.push({-e[v].a, v}); a2.push({e[v].b - e[v].a, v}); inqueue[i] = 2; b1.push({e[i].a - e[i].b, i}); b2.push({-e[i].b, i}); } else if (delta2 == ma) { int v = b2.top().nd; inqueue[v] = 0; inqueue[i] = 2; b1.push({e[i].a - e[i].b, i}); b2.push({-e[i].b, i}); } else { int u = a2.top().nd, v = b2.top().nd; inqueue[v] = 0; inqueue[i] = 1; a1.push({-e[i].a, i}); a2.push({e[i].b - e[i].a, i}); inqueue[u] = 2; b1.push({e[u].a - e[u].b, u}); b2.push({-e[u].b, u}); } } } cout << ans; return 0; }

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:26:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:27:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...