Submission #1082049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082049		Dennis_Jason	Hiring (IOI09_hiring)	C++14	100 / 100	608 ms	54104 KiB

hiring

#include <bits/stdc++.h>
#define NMAX 2005
#define pb push_back
#define eb emplace_back
#define MOD 100003
#define nl '\n'
#define LLONG_MAX 9223372036854775807
#define pii pair<double,double>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
#define INF 2147483647
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ================DEMONSTRATION===================


    =====================END========================
 */
struct pers{
    double r,s,q;
    int ind;
};
int n,budget;
vector<pers>v;
int ans,ind;
double cost;
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>budget;
    v.resize(n+1);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].s>>v[i].q;
        v[i].r=(v[i].s/v[i].q);
        v[i].ind=i;
    }
    auto cmp=[&](pers a,pers b)
    {
        return a.r<b.r;
    };
    sort(v.begin()+1,v.end(),cmp);

    double total=0;
    priority_queue<double,vector<double>>pq;
    for(int i=1;i<=n;++i)
    {
       pq.push(v[i].q);
       total+=v[i].q;
       double maxi=budget/v[i].r;
       while(total>maxi)
       {
           total-=pq.top();
           pq.pop();
       }
       int nr=pq.size();
       double aux=total*v[i].r;
       if(nr>ans ||(nr==ans && aux<cost))
       {
           ans=nr;
           cost=aux;
           ind=i;
       }
    }
    priority_queue<pii,vector<pii>>heap;
    total=0;
    map<int,int>mp;
    for(int i=1;i<=ind;++i)
    {
        heap.push({v[i].q,v[i].ind});
        total+=v[i].q;
        mp[v[i].ind]=1;
    }
    double maxi=budget/v[ind].r;
    while(total>maxi)
    {
        auto x=heap.top();
        heap.pop();
        total-=x.first;
        mp[x.second]=0;
    }
    cout<<ans<<nl;
    for(int i=1;i<=n;++i)
    {
        if(mp[i])
            cout<<i<<nl;
    }
    return 0;
}

Compilation message (stderr)

hiring.cpp:7: warning: "LLONG_MAX" redefined
    7 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from hiring.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

• Subtask 1: 30 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6