Submission #228687

#	Time	Username	Problem	Language	Result	Execution time	Memory
228687		osaaateiasavtnl	Hiring (IOI09_hiring)	C++14	64 / 100	1595 ms	24660 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 5e5 + 7;
int n, W;
struct Chel {
    int s, q, i;
} a[N];  
bool comp(Chel a, Chel b) {
    //return (a.s/a.q) < (b.s/b.q);
    return a.s * b.q < b.s * a.q;
}   
bool compq(int i, int j) {
    return a[i].q < a[j].q;
}   
bool ls(ii a, ii b) {
    return a.f * b.s < b.f * a.s;
}

int posq[N];
bool used[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> W;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].s >> a[i].q;
        a[i].i = i;
    }   
    sort(a, a + n, comp);

    vector <ii> t;
    for (int i = 0; i < n; ++i)
        t.app(mp(a[i].q, i));
    sort(all(t));
    for (int i = 0; i < n; ++i)
        posq[t[i].s] = i + 1;

    int ans = 0;
    ii pay = {0, 1};
    int ans_i = -1;
    for (int i = 0; i < n; ++i) {
        used[posq[i]] = 1;
        int sum = 0, k = 0;
        for (int j = 1; j <= n; ++j) {
            if (used[j]) {
                sum += t[j - 1].f;
                ++k;

                if (sum * a[i].s <= W * a[i].q) {
                    ii np = mp(sum * a[i].s, a[i].q);
                    if (k > ans || (k == ans && ls(np, pay))) {
                        ans = k;
                        pay = np;
                        ans_i = i;
                    }
                }   

            }   
        }   
    }
    cout << ans << endl;

    if (ans > 0) {
    vector <ii> t;
    for (int i = 0; i <= ans_i; ++i) {
        t.app(mp(a[i].q, a[i].i));
    }       
    sort(all(t));
    for (int i = 0; i < ans; ++i)
        cout << t[i].s + 1 << ' ';
    cout << endl;           
    }   

}

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