Submission #881723

#TimeUsernameProblemLanguageResultExecution timeMemory
881723alexddSchools (IZhO13_school)C++17
0 / 100
1225 ms8628 KiB
#include<bits/stdc++.h>
using namespace std;
const int NRIT = 3e7;
int n,m,s;
pair<int,pair<int,int>> v[300005];
int unde[300005];
mt19937 rnd(293123);
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        v[i] = {a-b,{a,b}};
    }
    sort(v+1,v+1+n);
    for(int i=1;i<=s;i++)
    {
        unde[i]=2;
    }
    for(int i=1;i<=m;i++)
    {
        unde[i]=1;
    }
    for(int pas=0;pas<NRIT;pas++)
    {
        int x = rnd()%n;
        int y = rnd()%n;
        if(unde[x]==unde[y])
            continue;
        if(unde[y]==0)
            swap(x,y);
        if(unde[x]==0)
        {
            if(unde[y]==1)
            {
                if(v[x].second.first - v[y].second.first > 0)
                    swap(unde[x],unde[y]);
            }
            else
            {
                if(v[x].second.second - v[y].second.second > 0)
                    swap(unde[x],unde[y]);
            }
        }
        else
        {
            if(unde[x]==2)
                swap(x,y);
            if(v[x].second.second - v[x].second.first + v[y].second.first - v[y].second.second > 0)
            {
                swap(unde[x],unde[y]);
            }
        }
    }
    long long sum=0;
    for(int i=0;i<n;i++)
    {
        if(unde[i]==1)
            sum += v[i].second.first;
        else if(unde[i]==2)
            sum += v[i].second.second;
    }
    cout<<sum;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...