Submission #673577

#	Time	Username	Problem	Language	Result	Execution time	Memory
673577		ReLice	Schools (IZhO13_school)	C++14	100 / 100	276 ms	27172 KiB

school

#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 (stderr)

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 / 100