Submission #13221

#	Time	Username	Problem	Language	Result	Execution time	Memory
13221		dohyun0324	Schools (IZhO13_school)	C++98	100 / 100	200 ms	14964 KiB

school

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> ppair;
typedef long long ll;
int n,m,s,ch[300010];
ll sum,dap;
priority_queue<ppair>q1;
priority_queue<ppair>q3;
priority_queue<ppair,vector<ppair>,greater<ppair> >dat;
priority_queue<ppair>q2;
struct data{
    int x,y;
    bool operator<(const data&r)const{
        return x>r.x;
    }
}a[300010];
struct data2{
    int x,p;
    bool operator<(const data2&r)const{
        return x>r.x;
    }
}arr[300010];
int main()
{
    int i,pos;
    scanf("%d %d %d",&n,&m,&s);
    for(i=1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1);
    for(i=1;i<=m;i++) arr[i].x=a[i].y-a[i].x, arr[i].p=i;
    sort(arr+1,arr+m+1);
    for(i=1;i<=m;i++) sum+=a[i].x;
    for(i=m+1;i<=n;i++) q3.push(make_pair(a[i].y,i));
    for(i=m+1;i<=m+s;i++)
    {
        pos=q3.top().second;
        sum+=a[pos].y;
        q1.push(make_pair(a[pos].x-a[pos].y,pos));
        dat.push(make_pair(a[pos].y,pos));
        q3.pop();
        ch[pos]=1;
    }
    for(i=m+1;i<=n;i++)
    {
        if(ch[i]) continue;
        q2.push(make_pair(a[i].x,i));
    }
    if(dap<sum) dap=sum;
    for(i=1;i<=min(m,s);i++)
    {
        while(dat.size() && ch[dat.top().second]==0) dat.pop();
        while(q1.size() && ch[q1.top().second]==0) q1.pop();
        sum+=arr[i].x;
        if(q2.size()==0 || q1.top().first>=q2.top().first-dat.top().first)
        {
            sum+=q1.top().first;
            ch[q1.top().second]=0;
        }
        else
        {
            sum+=q2.top().first-dat.top().first;
            q2.pop(); ch[dat.top().second]=0; q2.push(make_pair(a[dat.top().second].x,dat.top().second));
        }
        if(dap<sum) dap=sum;
    }
    printf("%lld",dap);
    return 0;
}

• Subtask 1: 100 / 100