oj.uz

Submission #477089

# Submission time Handle Problem Language Result Execution time Memory
477089 2021-09-30T08:59:00 Z ogibogi2004 Schools (IZhO13_school) C++14
85 / 100
 240 ms 11312 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=3e5+6;
int n,m,s;
struct city
{
    ll a,b;
    bool operator<(city const& other)const
    {
        if(a-b!=other.a-other.b)return a-b>other.a-other.b;
        return make_pair(a,b)>make_pair(a,b);
    }
};
city c[MAXN];
ll best1[MAXN],best2[MAXN];
priority_queue<ll>pq;
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i].a>>c[i].b;
    }
    sort(c+1,c+n+1);
    best1[0]=0;
    ll sum=0;
    /*for(int i=1;i<=n;i++)
    {
        cout<<c[i].a<<" "<<c[i].b<<endl;
    }*/
    for(int i=1;i<=n;i++)
    {
        sum+=c[i].a;
        pq.push(-c[i].a);
        if(i>m)
        {
            sum+=pq.top();
            pq.pop();
        }
        best1[i]=sum;
    }
    sum=0;
    best2[n+1]=0;
    for(int i=n;i>=1;i--)
    {
        sum+=c[i].b;
        pq.push(-c[i].b);
        if(n-i+1>s)
        {
            sum+=pq.top();
            pq.pop();
        }
        best2[i]=sum;
    }
    ll ans=0;
    for(int i=m;i+s<=n+1;i++)
    {
        ans=max(ans,best1[i]+best2[i+1]);
    }
    /*for(int i=1;i<=n;i++)cout<<best1[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<best2[i]<<" ";
    cout<<endl;*/
    cout<<ans<<endl;
return 0;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 5 ms 472 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Incorrect 4 ms 460 KB Output isn't correct
10 Incorrect 4 ms 460 KB Output isn't correct
11 Correct 5 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Incorrect 31 ms 1820 KB Output isn't correct
14 Correct 62 ms 3084 KB Output is correct
15 Correct 129 ms 5356 KB Output is correct
16 Correct 163 ms 7552 KB Output is correct
17 Correct 182 ms 8668 KB Output is correct
18 Correct 197 ms 9268 KB Output is correct
19 Correct 238 ms 10032 KB Output is correct
20 Correct 240 ms 11312 KB Output is correct