oj.uz

Submission #348813

# Submission time Handle Problem Language Result Execution time Memory
348813 2021-01-15T19:23:52 Z nicolaalexandra Schools (IZhO13_school) C++14
100 / 100
 382 ms 13548 KB 
#include <bits/stdc++.h>
#define DIM 300010
using namespace std;

pair <int,int> v[DIM];
int a[DIM],b[DIM];
long long pref[DIM],suf[DIM];
multiset <int> s;
int n,nra,nrb,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>nra>>nrb;
    for (i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v[i] = make_pair(b[i]-a[i],i);
    }

    sort (v+1,v+n+1);

    long long sum = 0;
    for (i=1;i<=nra;i++){
        sum += a[v[i].second];
        s.insert(a[v[i].second]);
    }

    pref[nra] = sum;
    for (i=nra+1;i<=n;i++){
        sum += a[v[i].second];

        s.insert(a[v[i].second]);

        /// scad minimul din set
        sum -= *s.begin();
        s.erase(s.begin());

        pref[i] = sum;
    }


    sum = 0;
    s.clear();
    for (i=n-nrb+1;i<=n;i++){
        sum += b[v[i].second];
        s.insert(b[v[i].second]);
    }

    suf[n-nrb+1] = sum;

    for (i=n-nrb;i;i--){
        sum += b[v[i].second];
        s.insert(b[v[i].second]);

        sum -= *s.begin();
        s.erase(s.begin());

        suf[i] = sum;
    }

    long long sol = 0;
    for (i=0;i<=n;i++)
        sol = max (sol,pref[i] + suf[i+1]);
    cout<<sol;


    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 5 ms 620 KB Output is correct
11 Correct 5 ms 620 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 37 ms 2668 KB Output is correct
14 Correct 71 ms 3564 KB Output is correct
15 Correct 128 ms 5628 KB Output is correct
16 Correct 231 ms 12012 KB Output is correct
17 Correct 280 ms 10732 KB Output is correct
18 Correct 321 ms 10988 KB Output is correct
19 Correct 325 ms 11756 KB Output is correct
20 Correct 382 ms 13548 KB Output is correct