oj.uz

Submission #1041765

# Submission time Handle Problem Language Result Execution time Memory
1041765 2024-08-02T07:52:04 Z Phuoc Schools (IZhO13_school) C++14
100 / 100
 73 ms 11952 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4608 KB Output is correct
10 Correct 2 ms 4696 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 10 ms 7400 KB Output is correct
14 Correct 18 ms 7896 KB Output is correct
15 Correct 32 ms 8532 KB Output is correct
16 Correct 42 ms 10700 KB Output is correct
17 Correct 53 ms 10192 KB Output is correct
18 Correct 69 ms 10696 KB Output is correct
19 Correct 66 ms 11060 KB Output is correct
20 Correct 73 ms 11952 KB Output is correct