Submission #1034159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034159		vjudge1	Schools (IZhO13_school)	C++17	20 / 100	72 ms	14212 KiB

school

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
using namespace std;

int n, m, s;
const int maxn = 1e6 + 3;
const int inf = 1e9;
pll p[maxn + 3];
priority_queue<int, vector<int>, greater<int>>pq1, pq2;
ll l[maxn + 3], r[maxn + 3], ans;

bool cmp(pll a, pll b)
{
    return a.fi - a.se < b.fi - b.se;
}

int main()
{
  //  freopen("SCHOOL.INP", "r", stdin);
 //   freopen("SCHOOL.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i].fi >> p[i].se;
    }
    sort(p + 1, p + n + 1, cmp);
    /*for(int i = 1; i <= n; i++)
    {
        cout << p[i].first << ' ' << p[i].second << '\n';
    } cout << '\n';*/
    for(int i = 1; i <= s; i++)
    {
        pq1.push(p[i].se);
        ans += p[i].se;
        l[i] = ans;
    }
    for(int i = s + 1; i <= n; i++)
    {
        if(p[i].se > pq1.top() && !pq1.empty())
        {
            ans = ans + p[i].se - pq1.top();
        }
        l[i] = ans;
    }
    ll ans = 0;
    for(int i = n; i >= n - m + 1; i--)
    {
        pq2.push(p[i].fi);
        ans += p[i].fi;
        r[i] = ans;
    }
    //cout << ans;
    for(int i = n - m; i >= 1; i--)
    {
        if(p[i].fi > pq2.top() && !pq2.empty())
        {
            ans  = ans + p[i].fi - pq2.top();
        }
        r[i] = ans;
    }
     ans = -inf;
    for(int i = 1; i < n; i++)
    {
        ans = max(ans, l[i] + r[i + 1]);
    }
    cout << ans;
}

• Subtask 1: 20 / 100