oj.uz

Submission #703583

# Submission time Handle Problem Language Result Execution time Memory
703583 2023-02-27T17:51:11 Z raysh07 Schools (IZhO13_school) C++17
100 / 100
 190 ms 24164 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());

bool comp(pair<int, int> c, pair<int, int> d){
    return (c.first - c.second > d.first - d.second); //so high a will be first 
}
 
int calc(vector<pair<int, int>> ab, int x, int y)
{
    int n = ab.size();
    //cout<<n<<" "<<x<<" "<<y<<"\n";
    if (x+y==0) return 0;
    ab.push_back({INF, 0});
    
    sort(ab.begin(), ab.end(), comp);
    vector <int> s(n + 2, 0);
    vector <int> s2(n + 2, 0);
    
    multiset <int> a;
    
    s[0] = 0;
    for (int i=1; i<=n; i++){
        a.insert(ab[i].first);
        s[i] = s[i-1] + ab[i].first;
        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].second);
        s2[i-1] = s2[i] + ab[i].second;
        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]);
    }
    
    return ans;
}

void Solve() 
{
    int n, x, y;
    cin>>n>>x>>y;
    
    vector <pair<int, int>> a;
    for (int i=0; i<n; i++){
        int A, B;
        cin>>A>>B;
        
        a.push_back({A, B});
    }
    
    cout<<calc(a, x, y);
}

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 'long long int calc(std::vector<std::pair<long long int, long long int> >, long long int, long long int)':
school.cpp:31: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]
   31 |         if (a.size() > x){
      |             ~~~~~~~~~^~~
school.cpp:42: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]
   42 |         if (b.size() > y){
      |             ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 19 ms 3484 KB Output is correct
14 Correct 37 ms 5344 KB Output is correct
15 Correct 59 ms 8072 KB Output is correct
16 Correct 121 ms 17292 KB Output is correct
17 Correct 144 ms 19456 KB Output is correct
18 Correct 154 ms 19804 KB Output is correct
19 Correct 163 ms 21548 KB Output is correct
20 Correct 190 ms 24164 KB Output is correct