oj.uz

Submission #703580

# Submission time Handle Problem Language Result Execution time Memory
703580 2023-02-27T17:45:11 Z raysh07 Schools (IZhO13_school) C++17
10 / 100
 197 ms 27716 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;
    
    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=0; i<n; i++){
        a.insert(ab[i].first);
        s[i+1] = s[i] + ab[i].first;
        if (a.size() > x){
            s[i+1] -= *a.begin();
            a.erase(a.find(*a.begin()));
        }
    }
    
    multiset <int> b;
    
    for (int i=n-1; i>=0; i--){
        b.insert(ab[i].second);
        s2[i] = s2[i-1] + ab[i].second;
        if (b.size() > y){
            s2[i] -= *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:30: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]
   30 |         if (a.size() > x){
      |             ~~~~~~~~~^~~
school.cpp:41: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]
   41 |         if (b.size() > y){
      |             ~~~~~~~~~^~~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 328 KB Output isn't correct
7 Incorrect 2 ms 596 KB Output isn't correct
8 Incorrect 3 ms 796 KB Output isn't correct
9 Incorrect 3 ms 724 KB Output isn't correct
10 Incorrect 3 ms 716 KB Output isn't correct
11 Incorrect 2 ms 724 KB Output isn't correct
12 Incorrect 2 ms 720 KB Output isn't correct
13 Incorrect 20 ms 3924 KB Output isn't correct
14 Incorrect 40 ms 6332 KB Output isn't correct
15 Incorrect 76 ms 9828 KB Output isn't correct
16 Incorrect 137 ms 19100 KB Output isn't correct
17 Incorrect 148 ms 22072 KB Output isn't correct
18 Incorrect 153 ms 22512 KB Output isn't correct
19 Incorrect 165 ms 24620 KB Output isn't correct
20 Incorrect 197 ms 27716 KB Output isn't correct