Submission #881727

#	Time	Username	Problem	Language	Result	Execution time	Memory
881727		alexdd	Schools (IZhO13_school)	C++17	30 / 100	2095 ms	5200 KiB

school

#include<bits/stdc++.h>
using namespace std;
const int NRIT = 4e5;
const int proba = 1000;
const int NRSHUFFLES = 100;
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);
    long long mxm=0;
    for(int pas2=0;pas2<NRSHUFFLES;pas2++)
    {
        for(int i=1;i<=n;i++)
            unde[i]=0;
        for(int i=1;i<=s;i++)
            unde[i]=2;
        for(int i=1;i<=m;i++)
            unde[n-i+1]=1;
        for(int pas=0;pas<NRIT;pas++)
        {
            int x = rnd()%n + 1;
            int y = rnd()%n + 1;
            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 || rnd()%proba==0)
                        swap(unde[x],unde[y]);
                }
                else
                {
                    if(v[x].second.second - v[y].second.second > 0 || rnd()%proba==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 || rnd()%proba==0)
                {
                    swap(unde[x],unde[y]);
                }
            }
        }
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            if(unde[i]==1)
                sum += v[i].second.first;
            else if(unde[i]==2)
                sum += v[i].second.second;
        }
        mxm=max(mxm,sum);
        random_shuffle(v+1,v+1+n);
    }
    cout<<mxm;
    return 0;
}

• Subtask 1: 30 / 100