Submission #894478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894478	2023-12-28T10:54:22 Z	heeheeheehaaw	Schools (IZhO13_school)	C++17	25 / 100	317 ms	14780 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Incorrect	2 ms	4440 KB	Output isn't correct
5	Incorrect	1 ms	4444 KB	Output isn't correct
6	Incorrect	1 ms	4444 KB	Output isn't correct
7	Incorrect	4 ms	4444 KB	Output isn't correct
8	Correct	5 ms	4444 KB	Output is correct
9	Incorrect	4 ms	4444 KB	Output isn't correct
10	Incorrect	4 ms	4644 KB	Output isn't correct
11	Incorrect	4 ms	4444 KB	Output isn't correct
12	Incorrect	4 ms	4444 KB	Output isn't correct
13	Incorrect	31 ms	5080 KB	Output isn't correct
14	Incorrect	70 ms	7636 KB	Output isn't correct
15	Incorrect	148 ms	10720 KB	Output isn't correct
16	Correct	131 ms	10576 KB	Output is correct
17	Incorrect	208 ms	10888 KB	Output isn't correct
18	Incorrect	230 ms	11468 KB	Output isn't correct
19	Incorrect	281 ms	11968 KB	Output isn't correct
20	Incorrect	317 ms	14780 KB	Output isn't correct