oj.uz

Submission #85825

# Submission time Handle Problem Language Result Execution time Memory
85825 2018-11-21T17:24:42 Z Vardanyan Schools (IZhO13_school) C++14
100 / 100
 164 ms 26208 KB 
//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 300*1000+5;
bool cmp(pair<int,int> x,pair<int,int> y){
    return x.first-x.second>y.first-y.second;
}
long long A[N];
long long B[N];

int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    vector<pair<int,int> > v;
    for(int i = 1;i<=n;i++){
        int ai,bi;
        scanf("%d%d",&ai,&bi);
        v.push_back({ai,bi});
    }
    sort(v.begin(),v.end(),cmp);
 //   for(int i = 0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<endl;
	priority_queue<int> pq;
	long long now = 0;
    for(int i = 0;i<v.size();i++){
        pq.push(-v[i].first);
        now+=v[i].first;
        if(pq.size()>m){
            int x = -pq.top();
            now-=x;
            pq.pop();
        }
        A[i+1] = now;
    }
    while(pq.size()) pq.pop();
    now = 0;
    long long ans = 0;
    for(int i = v.size()-1;i>=0;i--){
        pq.push(-v[i].second);
        now+=v[i].second;
        if(pq.size()>s){
            int x = -pq.top();
            now-=x;
            pq.pop();
        }
        B[i+1] = now;
    }
    for(int i = m;i<=n-s;i++) ans = max(ans,A[i]+B[i+1]);
    cout<<ans<<endl;
	return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++){
                   ~^~~~~~~~~
school.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pq.size()>m){
            ~~~~~~~~~^~
school.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pq.size()>s){
            ~~~~~~~~~^~
school.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&s);
     ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&ai,&bi);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 668 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 4 ms 1012 KB Output is correct
8 Correct 4 ms 1088 KB Output is correct
9 Correct 5 ms 1160 KB Output is correct
10 Correct 6 ms 1160 KB Output is correct
11 Correct 6 ms 1308 KB Output is correct
12 Correct 4 ms 1308 KB Output is correct
13 Correct 23 ms 2704 KB Output is correct
14 Correct 42 ms 4408 KB Output is correct
15 Correct 79 ms 8012 KB Output is correct
16 Correct 100 ms 12072 KB Output is correct
17 Correct 119 ms 14972 KB Output is correct
18 Correct 135 ms 18132 KB Output is correct
19 Correct 158 ms 21700 KB Output is correct
20 Correct 164 ms 26208 KB Output is correct