oj.uz

Submission #477091

# Submission time Handle Problem Language Result Execution time Memory
477091 2021-09-30T09:00:34 Z ogibogi2004 Schools (IZhO13_school) C++14
100 / 100
 244 ms 10580 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;
    while(!pq.empty())pq.pop();
    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;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
100.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 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 33 ms 1796 KB Output is correct
14 Correct 62 ms 3108 KB Output is correct
15 Correct 113 ms 5380 KB Output is correct
16 Correct 131 ms 7608 KB Output is correct
17 Correct 175 ms 8016 KB Output is correct
18 Correct 192 ms 8560 KB Output is correct
19 Correct 211 ms 9272 KB Output is correct
20 Correct 244 ms 10580 KB Output is correct