oj.uz

Submission #13217

# Submission time Handle Problem Language Result Execution time Memory
13217 2015-02-04T07:41:51 Z dohyun0324 Schools (IZhO13_school) C++
25 / 100
 2000 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<=m;i++)
    {
        while(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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7444 KB Output is correct
2 Runtime error 0 ms 7440 KB SIGSEGV Segmentation fault
3 Execution timed out 2000 ms 7440 KB Program timed out
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 Execution timed out 2000 ms 7440 KB Program timed out
10 Execution timed out 2000 ms 7440 KB Program timed out
11 Incorrect 0 ms 7604 KB Output isn't correct
12 Incorrect 3 ms 7604 KB Output isn't correct
13 Execution timed out 2000 ms 7584 KB Program timed out
14 Incorrect 33 ms 10096 KB Output isn't correct
15 Correct 65 ms 13744 KB Output is correct
16 Incorrect 95 ms 14964 KB Output isn't correct
17 Incorrect 150 ms 12912 KB Output isn't correct
18 Incorrect 155 ms 13936 KB Output isn't correct
19 Incorrect 156 ms 12912 KB Output isn't correct
20 Incorrect 153 ms 13936 KB Output isn't correct