oj.uz

Submission #13218

# Submission time Handle Problem Language Result Execution time Memory
13218 2015-02-04T07:46:22 Z dohyun0324 Schools (IZhO13_school) C++
35 / 100
 143 ms 14964 KB 
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> ppair;
int sum,dap,n,m,s,ch[300010];
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();
        sum+=arr[i].x;
        if(q2.size()==0 || q1.top().first>=q2.top().first-dat.top().first)
        {
            sum+=q1.top().first;
            q1.pop(); ch[q1.top().second]=0;
        }
        else
        {
            sum+=q2.top().first-dat.top().first;
            q2.pop(); ch[dat.top().second]=0;
        }
        if(dap<sum) dap=sum;
    }
    printf("%d",dap);
    return 0;
}

Subtask #1
35.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7444 KB Output is correct
2 Correct 0 ms 7444 KB Output is correct
3 Correct 0 ms 7444 KB Output is correct
4 Correct 0 ms 7444 KB Output is correct
5 Correct 0 ms 7444 KB Output is correct
6 Incorrect 0 ms 7444 KB Output isn't correct
7 Incorrect 0 ms 7444 KB Output isn't correct
8 Correct 0 ms 7444 KB Output is correct
9 Incorrect 0 ms 7444 KB Output isn't correct
10 Incorrect 0 ms 7444 KB Output isn't correct
11 Incorrect 0 ms 7604 KB Output isn't correct
12 Incorrect 0 ms 7604 KB Output isn't correct
13 Incorrect 12 ms 7588 KB Output isn't correct
14 Incorrect 34 ms 10096 KB Output isn't correct
15 Correct 62 ms 13744 KB Output is correct
16 Incorrect 142 ms 14964 KB Output isn't correct
17 Incorrect 132 ms 12912 KB Output isn't correct
18 Incorrect 100 ms 13936 KB Output isn't correct
19 Incorrect 143 ms 12912 KB Output isn't correct
20 Incorrect 112 ms 13936 KB Output isn't correct