제출 #477091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477091		ogibogi2004	학교 설립 (IZhO13_school)	C++14	100 / 100	244 ms	10580 KiB

school

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=3e5+6;
int n,m,s;
struct city
{
    ll a,b;
    bool operator<(city const& other)const
    {
        if(a-b!=other.a-other.b)return a-b>other.a-other.b;
        return make_pair(a,b)>make_pair(a,b);
    }
};
city c[MAXN];
ll best1[MAXN],best2[MAXN];
priority_queue<ll>pq;
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i].a>>c[i].b;
    }
    sort(c+1,c+n+1);
    best1[0]=0;
    ll sum=0;
    /*for(int i=1;i<=n;i++)
    {
        cout<<c[i].a<<" "<<c[i].b<<endl;
    }*/
    for(int i=1;i<=n;i++)
    {
        sum+=c[i].a;
        pq.push(-c[i].a);
        if(i>m)
        {
            sum+=pq.top();
            pq.pop();
        }
        best1[i]=sum;
    }
    sum=0;
    best2[n+1]=0;
    while(!pq.empty())pq.pop();
    for(int i=n;i>=1;i--)
    {
        sum+=c[i].b;
        pq.push(-c[i].b);
        if(n-i+1>s)
        {
            sum+=pq.top();
            pq.pop();
        }
        best2[i]=sum;
    }
    ll ans=0;
    for(int i=m;i+s<=n;i++)
    {
        ans=max(ans,best1[i]+best2[i+1]);
    }
    /*for(int i=1;i<=n;i++)cout<<best1[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<best2[i]<<" ";
    cout<<endl;*/
    cout<<ans<<endl;
return 0;
}

• Subtask 1: 100 / 100