oj.uz

Submission #673577

# Submission time Handle Problem Language Result Execution time Memory
673577 2022-12-21T07:35:34 Z ReLice Schools (IZhO13_school) C++14
100 / 100
 276 ms 27172 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define pb push_back
#define fr first
#define sc second
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll N = 4e5 + 10 ;
const ll mod=1e9+7;
ll pr[N],suf[N];
void solve(){
    ll n,i,x,y,mx=-1;
    ll m,k,sum=0,c=0,j;
    cin>>n>>m>>k;
    ll a[n+1],b[n+1];
    vector <pair<ll,ll>> vec;
    vector <ll> v,v2;
    multiset<ll> st,st2;
    for(i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        vec.pb({a[i]-b[i],i});
    }
    sort(vec.rbegin(),vec.rend());
    v.pb(0);
    v2.pb(0);
    for(i=0;i<n;i++){
        v.pb(a[vec[i].sc]);
        v2.pb(b[vec[i].sc]);
    }
    if(!m && !k){
        cout<<0<<endl;
        return;
    }
    if(!k){
        sort(v.rbegin(),v.rend());
        for(i=0;i<m;i++) sum+=v[i];
        cout<<sum<<endl;
        return;
    }
    if(!m){
        sort(v2.rbegin(),v2.rend());
        for(i=0;i<k;i++) sum+=v2[i];
        cout<<sum<<endl;
        return;
    }
    for(i=1;i<=m;i++){
        st.insert(v[i]);
        sum+=v[i];
    }
    pr[m]=sum;
    for(i=m+1;i<=n;i++){
        if(v[i]>*st.begin()){
            sum-=*st.begin();
            st.erase(st.begin());
            sum+=v[i];
            st.insert(v[i]);
        }
        pr[i]=sum;
    }
    sum=0;
    for(i=n;i>n-k;i--){
        st2.insert(v2[i]);
        sum+=v2[i];
    }
    suf[n-k+1]=sum;
    for(i=n-k;i>0;i--){
        if(v2[i]>*st2.begin()){
            sum-=*st2.begin();
            st2.erase(st2.begin());
            sum+=v2[i];
            st2.insert(v2[i]);
        }
        suf[i]=sum;
    }
    for(i=m;i<=n-k;i++){
        mx=max(mx,pr[i]+suf[i+1]);
    }
    cout<<mx<<endl;
}
main(){
    //fre("");
    //start();
    ll t=1;
    //cin>>t;
    while(t--)solve();

}

Compilation message

school.cpp: In function 'void solve()':
school.cpp:17:12: warning: unused variable 'x' [-Wunused-variable]
   17 |     ll n,i,x,y,mx=-1;
      |            ^
school.cpp:17:14: warning: unused variable 'y' [-Wunused-variable]
   17 |     ll n,i,x,y,mx=-1;
      |              ^
school.cpp:18:18: warning: unused variable 'c' [-Wunused-variable]
   18 |     ll m,k,sum=0,c=0,j;
      |                  ^
school.cpp:18:22: warning: unused variable 'j' [-Wunused-variable]
   18 |     ll m,k,sum=0,c=0,j;
      |                      ^
school.cpp: At global scope:
school.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~

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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 33 ms 4036 KB Output is correct
14 Correct 55 ms 6332 KB Output is correct
15 Correct 96 ms 12332 KB Output is correct
16 Correct 178 ms 19140 KB Output is correct
17 Correct 209 ms 21760 KB Output is correct
18 Correct 221 ms 22220 KB Output is correct
19 Correct 243 ms 24128 KB Output is correct
20 Correct 276 ms 27172 KB Output is correct