Submission #201719

#	Time	Username	Problem	Language	Result	Execution time	Memory
201719		Shelby	학교 설립 (IZhO13_school)	C++11	20 / 100	2088 ms	26056 KiB

school

#include <bits/stdc++.h>
#define MAXN 300005
#define f first
#define s second
using namespace std;
typedef long long ll;

int a[MAXN],b[MAXN];
bool taken[MAXN];

set<pair<int,pair<int,int> >,greater<pair<int,pair<int,int> > > > mm;
set<pair<int,pair<int,int> >,greater<pair<int,pair<int,int> > > > ss;
multiset<pair<int,int> > tt;

vector< pair<int,int> > poma;
vector< pair<int,int> > pomb;
vector< pair<int,int> > not_taken;

int main()
{ int m,n,s,i,cnt=0,p;
long long sol=0;
scanf("%d%d%d",&n,&m,&s);

for(i=0;i<n;i++)
{
    scanf("%d%d",&a[i],&b[i]);

    poma.push_back( {a[i],i} );

    pomb.push_back( {b[i],i} );
}

sort(poma.begin(),poma.end(),greater<pair<int,int> >());

sort(pomb.begin(),pomb.end(),greater<pair<int,int> >());

for(i=0;i<m;i++)
{
    int tmp=poma[i].second;

    sol+=(ll)a[tmp];

    taken[tmp]=true;

    mm.insert( { b[tmp]-a[tmp] , {a[tmp],tmp} } );
}

for(i=0;i<n;i++)
{
    int tmp=pomb[i].second;

    if(taken[tmp]==false && cnt<s)
    {
        cnt++;

        sol+=(ll)b[tmp];

        taken[tmp]=true;

        ss.insert( { a[tmp]-b[tmp] , {-a[tmp],tmp } } );
    }

    if(taken[tmp]==false && cnt>=s) not_taken.push_back( {a[tmp],tmp} );
}

bool ok=true;

while(ok)
{
    pair<int,pair<int,int> > k=*mm.begin();   pair<int,pair<int,int> > l=*ss.begin();

    if((k.first+l.first)>0 || ( ((k.first+l.first)==0) && a[k.second.second]>a[l.second.second]) )
    {
        mm.erase(mm.begin());   ss.erase(ss.begin());

        mm.insert( { -l.first, {a[l.second.second],l.second.second} } );

        ss.insert( { -k.first, {-a[k.second.second],k.second.second} } );

        sol+=(ll)k.first+(ll)l.first;
    }
    else ok=false;
}

for(auto it=mm.begin();it!=mm.end();++it)
{
    pair<int,pair<int,int> > tmp=*it;

    tt.insert({a[tmp.second.second],tmp.s.s});
}

sort(not_taken.begin(),not_taken.end(),greater<pair<int,int> >());

p=0;

ok=true;

while(ok && p<not_taken.size() && !tt.empty())
{
    pair<int,int> kk=*tt.begin();

    if(kk.first<=not_taken[p].first)
    {
        int f=not_taken[p].s;

        tt.erase(tt.begin());

        sol+=(ll)not_taken[p].first-(ll)kk.first;

        mm.erase( mm.find( { b[kk.second]-a[kk.second] , { a[kk.second],kk.second } } ) );

        mm.insert( { b[f]-a[f] , { a[f],f } } );

        p++;
    }
    else ok=false;
}

ok=true;

while(ok)
{
    pair<int,pair<int,int> > k=*mm.begin();   pair<int,pair<int,int> > l=*ss.begin();

    if((k.first+l.first)>0)
    {
        mm.erase(mm.begin());   ss.erase(ss.begin());

        mm.insert( { -l.first, {a[l.second.second],l.second.second} } );

        ss.insert( { -k.first, {-a[k.second.second],k.second.second} } );

        sol+=(ll)k.first+(ll)l.first;
    }
    else ok=false;
}

printf("%lld\n",sol);
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(ok && p<not_taken.size() && !tt.empty())
             ~^~~~~~~~~~~~~~~~~
school.cpp:22:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d%d",&n,&m,&s);
 ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a[i],&b[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100