Submission #962171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
962171	2024-04-13T08:20:04 Z	sleepntsheep	Schools (IZhO13_school)	C++17	100 / 100	123 ms	13856 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	652 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	3 ms	604 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	15 ms	1940 KB	Output is correct
14	Correct	23 ms	3012 KB	Output is correct
15	Correct	28 ms	4884 KB	Output is correct
16	Correct	113 ms	9912 KB	Output is correct
17	Correct	102 ms	9844 KB	Output is correct
18	Correct	92 ms	9760 KB	Output is correct
19	Correct	103 ms	10508 KB	Output is correct
20	Correct	123 ms	13856 KB	Output is correct