Submission #1041765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041765		Phuoc	Schools (IZhO13_school)	C++14	100 / 100	73 ms	11952 KiB

school

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = (ll)(1e9) + 7LL;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 300010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int numCity, numMusic, numSport;
pair <int, int> Demand[MAX];

void init(){    
    cin >> numCity >> numMusic >> numSport;
    FOR(i, 1, numCity)  cin >> Demand[i].fi >> Demand[i].se;
}

bool cmp(pair <int, int> a, pair <int, int> b){
    return (a.se - a.fi < b.se - b.fi);  
}

long long up[MAX], down[MAX];

void solve(){
    sort(Demand + 1, Demand + numCity + 1, cmp);
    priority_queue <long long, vector <long long>, greater <long long> > pq;
    long long sum = 0;
    FOR(i, 1, numCity){
        pq.push(Demand[i].fi);
        sum += Demand[i].fi;
        if(pq.size() > numMusic){
            sum -= pq.top();
            pq.pop();
        }
        up[i] = sum;
    }   
    while(pq.size()) pq.pop();
    sum = 0;
    FORD(i, numCity, 1){
        pq.push(Demand[i].se);
        sum += Demand[i].se;
        if(pq.size() > numSport){
            sum -= pq.top();
            pq.pop();
        } 
        down[i] = sum;
    }
    long long ans = 0;
    FOR(i, numMusic, numCity - numSport){
        // cout << up[i] << ' ' << down[i + 1] << el;
        maximize(ans, up[i] + down[i + 1]);
    }
    cout << ans;
}           

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        solve();
    }
    
    return 0;
}


 
/*** ROAD TO VOI 2025 ***/

Compilation message (stderr)

school.cpp: In function 'void solve()':
school.cpp:79:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if(pq.size() > numMusic){
      |            ~~~~~~~~~~^~~~~~~~~~
school.cpp:90:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |         if(pq.size() > numSport){
      |            ~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100