제출 #881724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881724		alexdd	학교 설립 (IZhO13_school)	C++17	35 / 100	1693 ms	5120 KiB

school

#include<bits/stdc++.h>
using namespace std;
const int NRIT = 4e7;
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[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)
                    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=1;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;
}

• Subtask 1: 35 / 100