Submission #201688

#	Time	Username	Problem	Language	Result	Execution time	Memory
201688		Shelby	Schools (IZhO13_school)	C++11	5 / 100	278 ms	18380 KiB

school

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

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

set<pair<int,int>,greater<pair<int,int> > > mm;
set<pair<int,int>,greater<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] , 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] , tmp } );
    }

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

bool ok=true;

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

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

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

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

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

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

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

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

p=0;

ok=true;

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

    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:18:21: warning: unused variable 'p' [-Wunused-variable]
 { int m,n,s,i,cnt=0,p;
                     ^
school.cpp:64:6: warning: unused variable 'ok' [-Wunused-variable]
 bool ok=true;
      ^~
school.cpp:20: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:24: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: 5 / 100