Submission #962171

#	Time	Username	Problem	Language	Result	Execution time	Memory
962171		sleepntsheep	Schools (IZhO13_school)	C++17	100 / 100	123 ms	13856 KiB

school

#include <cstdlib>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
using namespace std;

using ll = long long;
using db = long double;
using str = string; // yay python!
using vi = vector<int>;

#define A(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

template <typename T>
struct rempq
{
    priority_queue<T> p, q;
    int sz=0;
    void push(T a)
    {
        p.push(a);
        ++sz;
    }

    void rem(T a)
    {
        q.push(a);
        --sz;
    }

    void pop()
    {
        while (p.size() && q.size() && q.top() == p.top())
        {
            q.pop();
            p.pop();
        }
        --sz;
        p.pop();
    }
    T top()
    {
        while (p.size() && q.size() && q.top() == p.top())
        {
            q.pop();
            p.pop();
        }
        return p.top();
    }

    int size()
    {
        return sz;
    }
};

int main()
{
    ShinLena;
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vi a(n), b(n);
    for(int i=0;i<n;++i)
        cin>>a[i]>>b[i];


    long long mcmf = 0;

    rempq<pair<int, int>> aa, bb, ra, rb;
    for (int i=0;i<n;++i)
        aa.push({a[i], i}), bb.push({b[i], i});


    while (k1 + k2)
    {
        int op=-1;
        int flow = 0;

        if (k1&&aa.size()) op=1, flow = aa.top().first;
        if (k2&&bb.size() && bb.top().first > flow) op=2, flow=bb.top().first;
        if (k1&&ra.size() && bb.size() && ra.top().first + bb.top().first  > flow) op=3, flow=bb.top().first+ra.top().first;
        if (k2&&rb.size() && aa.size () && rb.top().first + aa.top().first>flow)op=4, flow=aa.top().first+rb.top().first;

        mcmf += flow;
        if (op==1)
        {
            int i=aa.top().second;
            aa.pop();
            bb.rem({b[i], i});
            rb.push({-a[i]+b[i], i});
            --k1;
        }
        else if(op==2)
        {
            int i=bb.top().second;
            bb.pop();
            aa.rem({a[i], i});
            ra.push({-b[i]+a[i], i});
            --k2;
        }
        else if(op==3)
        {
            int i=bb.top().second, j=ra.top().second;
            ra.pop();
            bb.pop();
            aa.rem({a[i], i});
            ra.push({-b[i]+a[i], i});
            rb.push({-a[j]+b[j], j});
            --k1;
        }
        else if(op==4)
        {
            int i=aa.top().second, j=rb.top().second;
            rb.pop();
            aa.pop();
            bb.rem({b[i], i});
            rb.push({-a[i]+b[i], i});
            ra.push({-b[j]+a[j], j});
            --k2;
        }
    }

    cout << mcmf;

    return 0;
}

• Subtask 1: 100 / 100