oj.uz

Submission #703582

# Submission time Handle Problem Language Result Execution time Memory
703582 2023-02-27T17:49:16 Z raysh07 Schools (IZhO13_school) C++17
100 / 100
 181 ms 19504 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, x, y;
const int maxn = 3e5 + 69;
pair<int, int> ab[maxn];
int s[maxn];
int s2[maxn];

bool comp(pair<int, int> c, pair<int, int> d){
    return (c.f - c.s > d.f - d.s); //so high a will be first 
}

void Solve() 
{
    cin>>n>>x>>y;
    
    for (int i=1; i<=n; i++)
    cin>>ab[i].f>>ab[i].s;
    
    sort(ab+1, ab+n+1, comp);
    
    multiset <int> a;
    
    s[0] = 0;
    for (int i=1; i<=n; i++){
        a.insert(ab[i].f);
        s[i] = s[i-1] + ab[i].f;
        if (a.size() > x){
            s[i] -= *a.begin();
            a.erase(a.find(*a.begin()));
        }
    }
    
    multiset <int> b;
    
    for (int i=n; i>=1; i--){
        b.insert(ab[i].s);
        s2[i-1] = s2[i] + ab[i].s;
        if (b.size() > y){
            s2[i-1] -= *b.begin();
            b.erase(b.find(*b.begin()));
        }
    }
    
    int ans = 0;
    for (int i=x; i<=n-y; i++){
        ans = max(ans, s[i] + s2[i]);
    }
    
    cout<<ans<<"\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
   // cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message

school.cpp: In function 'void Solve()':
school.cpp:34:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |         if (a.size() > x){
      |             ~~~~~~~~~^~~
school.cpp:45:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |         if (b.size() > y){
      |             ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 17 ms 2944 KB Output is correct
14 Correct 35 ms 4144 KB Output is correct
15 Correct 55 ms 5584 KB Output is correct
16 Correct 114 ms 14248 KB Output is correct
17 Correct 134 ms 16056 KB Output is correct
18 Correct 145 ms 15844 KB Output is correct
19 Correct 159 ms 17496 KB Output is correct
20 Correct 181 ms 19504 KB Output is correct