제출 #1324587

#제출 시각아이디문제언어결과실행 시간메모리
1324587hungez1902학교 설립 (IZhO13_school)C++20
100 / 100
79 ms16256 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN/4;
int n,m,s;
ll a[300005],b[300005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s;
    vector<pair<ll,ll>> v(n);
    for(int i=0;i<n;i++) 
        cin>>v[i].first>>v[i].second;
    sort(v.begin(), v.end(), [](const pair<ll,ll>& x,const pair<ll,ll>& y)
    {
        return (x.first - x.second) > (y.first - y.second);
    });
    for(int i=0;i<n;i++)
    {
        a[i]=v[i].first; 
        b[i]=v[i].second; 
    }
    vector<ll> dp1(n, NEG), dp2(n, NEG);
    if(m==0)
    {
        for(int i=0;i<n;i++) dp1[i]=0;
    } 
    else 
    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        ll sum=0;
        for(int i=0;i<n;i++)
        {
            pq.push(a[i]); sum += a[i];
            if(pq.size()>m)
            { 
                sum -= pq.top(); 
                pq.pop(); 
            }
            if(pq.size()==m) dp1[i]=sum;
        }
    }
    if(s==0)
    {
        for(int i=0;i<n;i++) dp2[i]=0;
    } 
    else 
    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        ll sum=0;
        for(int i=n-1;i>=0;i--)
        {
            pq.push(b[i]); sum += b[i];
            if(pq.size()>s)
            { 
                sum -= pq.top(); 
                pq.pop(); 
            }
            if(pq.size()==s) dp2[i]=sum;
        }
    }
    ll ans = NEG;
    if(m==0)
    {
        if(dp2[0]!=NEG) ans = max(ans, dp2[0]);
    } 
    else if(s==0)
    {
        if(dp1[n-1]!=NEG) ans = max(ans, dp1[n-1]);
    } 
    else 
    {
        int L = m-1, R = n-s-1;
        if(L<=R)
        {
            for(int i=L;i<=R;i++)
            {
                if(dp1[i]!=NEG && dp2[i+1]!=NEG) ans = max(ans, dp1[i]+dp2[i+1]);
            }
        }
    }
    if(ans==NEG) ans=0;
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...