oj.uz

Submission #13220

# Submission time Handle Problem Language Result Execution time Memory
13220 2015-02-04T08:25:57 Z dohyun0324 Schools (IZhO13_school) C++
50 / 100
 183 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();
        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;
        }
        if(dap<sum) dap=sum;
    }
    printf("%lld",dap);
    return 0;
}

Subtask #1
50.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 Correct 0 ms 7444 KB Output is correct
11 Incorrect 0 ms 7604 KB Output isn't correct
12 Correct 2 ms 7604 KB Output is correct
13 Incorrect 18 ms 7588 KB Output isn't correct
14 Incorrect 24 ms 10096 KB Output isn't correct
15 Correct 64 ms 13744 KB Output is correct
16 Correct 129 ms 14964 KB Output is correct
17 Incorrect 133 ms 12912 KB Output isn't correct
18 Incorrect 153 ms 13936 KB Output isn't correct
19 Incorrect 169 ms 12912 KB Output isn't correct
20 Incorrect 183 ms 13936 KB Output isn't correct