Submission #1034184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034184		vjudge1	학교 설립 (IZhO13_school)	C++17	100 / 100	76 ms	14932 KiB

school

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

ll n, m, s;
const int maxn = 2e6 + 3;
const ll inf = 1e18;
pll p[maxn + 3];
priority_queue<ll, vector<ll>, greater<ll>>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(!pq1.empty() && p[i].se >= pq1.top())
        {
            ans = ans + p[i].se - pq1.top();
            pq1.pop();
            pq1.push(p[i].se);
        }
        l[i] = ans;
    }
    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(!pq2.empty() && p[i].fi >= pq2.top())
        {
            ans  = ans + p[i].fi - pq2.top();
            pq2.pop();
            pq2.push(p[i].fi);
        }
        r[i] = ans;
    }
    ans = -inf;
    for(int i = s; i + m - 1 <= n; i++)
    {
        ans = max(ans, l[i] + r[i + 1]);
    }
    cout << ans;
}

• Subtask 1: 100 / 100