oj.uz

답안 #870956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870956 2023-11-09T15:17:49 Z anha3k25cvp 학교 설립 (IZhO13_school) C++14
100 / 100
 85 ms 16144 KB 
#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

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);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 9 ms 2544 KB Output is correct
14 Correct 23 ms 3544 KB Output is correct
15 Correct 34 ms 5492 KB Output is correct
16 Correct 46 ms 9576 KB Output is correct
17 Correct 59 ms 11320 KB Output is correct
18 Correct 76 ms 11924 KB Output is correct
19 Correct 72 ms 12704 KB Output is correct
20 Correct 85 ms 16144 KB Output is correct