Submission #894478

#	Time	Username	Problem	Language	Result	Execution time	Memory
894478		heeheeheehaaw	Schools (IZhO13_school)	C++17	25 / 100	317 ms	14780 KiB

school

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct yes
{
    int p, v;
};

yes v1[300005];
yes v2[300005];
bool vis1[300005];
bool vis2[300005];
bool luat[300005];

bool beg(yes a, yes b)
{
    return a.p < b.p;
}

bool cmp(yes a, yes b)
{
    return a.v > b.v;
}

bool cmp2(int a, int b)
{
    int dif1 = (v1[a].v - v2[a].v), dif2 = (v1[b].v - v2[b].v);
    if(dif1 == dif2)
        return v1[a].v > v1[b].v;
    return dif1 < dif2;
}

bool cmp3(yes a, yes b)
{
    return a.v < b.v;
}

bool cmp4(int a, int b)
{
    int dif1 = (v2[a].v - v1[a].v), dif2 = (v2[b].v - v1[b].v);
    if(dif1 == dif2)
        return v2[a].v > v2[b].v;
    return dif1 < dif2;
}

signed main()
{
    int n, m, s;
    cin>>n>>m>>s;
    vector<int> p;
    int rez = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>v1[i].v>>v2[i].v;
        v1[i].p = v2[i].p = i;
        p.push_back(i);
        vis1[i] = true;
        rez += v1[i].v;
    }

    sort(p.begin(), p.end(), cmp2);
    int cm = n, cs = 0, poz = -1;
    while(cm > m && cs < s)
    {
        poz++;
        cm--, cs++;
        vis1[p[poz]] = false;
        vis2[p[poz]] = true;
        rez -= v1[p[poz]].v;
        rez += v2[p[poz]].v;
    }

    if(cm > m)
    {
        sort(v1 + 1, v1 + n + 1, cmp3);
        poz = 0;
        while(cm > m)
        {
            poz++;
            if(!vis2[v1[poz].p])
                cm--, rez -= v1[poz].v;
        }
    }

    int fin = rez;
    rez = 0;
    for(int i = 1; i <= n; i++)
        vis1[i] = vis2[i] = false;
    cm = 0, cs = n, poz = -1;

    p.clear();
    sort(v1 + 1, v1 + n + 1, beg);
    for(int i = 1; i <= n; i++)
    {
        p.push_back(i);
        vis2[i] = true;
        rez += v2[i].v;
    }

    sort(p.begin(), p.end(), cmp4);
    while(cm < m && cs > s)
    {
        poz++;
        cm++, cs--;
        vis1[p[poz]] = true;
        vis2[p[poz]] = false;
        rez += v1[p[poz]].v;
        rez -= v2[p[poz]].v;
    }

    if(cs > s)
    {
        sort(v2 + 1, v2 + n + 1, cmp3);
        poz = 0;
        while(cs > s)
        {
            poz++;
            if(!vis1[v2[poz].p])
                cs--, rez -= v2[poz].v;
        }
    }

    fin = min(fin, rez);
    cout<<fin;

    return 0;
}

• Subtask 1: 25 / 100