oj.uz

Submission #13219

# Submission time Handle Problem Language Result Execution time Memory
13219 2015-02-04T07:50:34 Z dohyun0324 Schools (IZhO13_school) C++
40 / 100
 195 ms 14964 KB 
#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();
        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("%lld",dap);
    return 0;
}

Subtask #1
40.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 1 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 3 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 33 ms 10096 KB Output isn't correct
15 Correct 64 ms 13744 KB Output is correct
16 Correct 139 ms 14964 KB Output is correct
17 Incorrect 139 ms 12912 KB Output isn't correct
18 Incorrect 148 ms 13936 KB Output isn't correct
19 Incorrect 162 ms 12912 KB Output isn't correct
20 Incorrect 195 ms 13936 KB Output isn't correct