Submission #201706

#	Time	Username	Problem	Language	Result	Execution time	Memory
201706		Shelby	Schools (IZhO13_school)	C++11	20 / 100	2081 ms	25664 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<int> tt;

vector< pair<int,int> > poma;
vector< pair<int,int> > pomb;
vector<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]);
}

bool ok=true;

/*for(auto it=mm.begin();it!=mm.end();++it)
{
    auto f=*it;

    cout << f.second.f << endl;
}*/

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

    //cout << k.first << " " << l.first << " " << k.second.first << " " << a[l.second.second] << endl;

    /*for(auto it=mm.begin();it!=mm.end();++it)
    {
        auto f=*it;

        cout << f.first << " " <<f.second.f  << " " << f.s.s<< endl;
    }
    printf("-------\n");

    for(auto it=ss.begin();it!=ss.end();++it)
    {
        auto f=*it;

        cout << f.first << " " <<f.second.f  << " " << f.s.s<< endl;
    }
    printf("*********************************\n");*/

    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]);
}

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

p=0;

ok=true;

//cout << sol << endl;

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

    //cout << kk << " " << not_taken[p] << endl;

    if(kk<not_taken[p])
    {
        tt.erase(tt.begin());

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

        p++;
    }
    else ok=false;
}

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

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:125: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