oj.uz

Submission #339316

# Submission time Handle Problem Language Result Execution time Memory
339316 2020-12-25T04:08:28 Z talant117408 Schools (IZhO13_school) C++17
100 / 100
 131 ms 15084 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

bool cmp(pll a, pll b){
    return a.first-a.second < b.first-b.second;
}

int main(){
    do_not_disturb
    
    ll n, music, sport;
    cin >> n >> music >> sport;
    vector <pll> want(n+1);
    for(int i = 1; i <= n; i++){
        cin >> want[i].first >> want[i].second;
    }
    
    ll summ[n+2], sums[n+2];
    sums[0] = summ[n+1] = 0;
    ll sum = 0;
    priority_queue <ll, vector <ll>, greater<ll>> M, S;
    
    sort(want.begin()+1, want.end(), cmp);
    
    for(int i = 1; i <= n; i++){
        sum += want[i].second;
        S.push(want[i].second);
        if(i > sport){
            sum -= S.top();
            S.pop();
        }
        sums[i] = sum;
    }
    
    sum = 0;
    
    for(int i = n; i; i--){
        sum += want[i].first;
        M.push(want[i].first);
        if(n-i >= music){
            sum -= M.top();
            M.pop();
        }
        summ[i] = sum;
    }
    
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        ans = max(ans, sums[i]+summ[i+1]);
    }
    
    cout << ans;
        
    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 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 15 ms 2300 KB Output is correct
14 Correct 34 ms 4080 KB Output is correct
15 Correct 69 ms 7344 KB Output is correct
16 Correct 79 ms 9572 KB Output is correct
17 Correct 94 ms 11372 KB Output is correct
18 Correct 112 ms 12216 KB Output is correct
19 Correct 114 ms 13164 KB Output is correct
20 Correct 131 ms 15084 KB Output is correct