Submission #1040385

#TimeUsernameProblemLanguageResultExecution timeMemory
1040385Neco_arcSchools (IZhO13_school)C++17
100 / 100
223 ms29776 KiB
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Schools"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 3e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, n1, n2;
pair<int, int> a[maxn];
multiset<int> S1;
set<pair<int, int>> S2, S3;
ll Sum;

void solve()
{

    cin >> n >> n1 >> n2;
    fi(i, 1, n) cin >> a[i].first >> a[i].second;

    sort(a + 1, a + 1 + n, greater<>());
    fi(i, 1, n) {
        if(i <= n1) S1.insert(a[i].second - a[i].first), Sum += a[i].first;
        else {
            S2.insert({a[i].first, i});
            S3.insert({a[i].second, i});
        }
    }

    fi(_, 1, n2) {
        int th = 0, Max = -1e18;

        ll val = *S1.rbegin() + S2.rbegin()->first;
        if(val > Max) {
            Max = val, th = 1;
        }

        val = S3.rbegin()->first;
        if(val > Max) {
            Max = val, th = 2;
        }

        Sum += Max;
        if(th == 1) {
            int id = S2.rbegin() -> second;
            S1.erase(prev(S1.end()));
            S1.insert({a[id].second - a[id].first});

            S2.erase({a[id].first, id});
            S3.erase({a[id].second, id});
        }

        if(th == 2) {
            int id = S3.rbegin() -> second;

            S2.erase({a[id].first, id});
            S3.erase({a[id].second, id});
        }

    }

    cout << Sum;

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

school.cpp: In function 'void solve()':
school.cpp:45:27: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   45 |         int th = 0, Max = -1e18;
      |                           ^~~~~
school.cpp: In function 'int main()':
school.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...