oj.uz

답안 #970954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970954 2024-04-27T15:58:22 Z Bilyana Hiring (IOI09_hiring) C++17
56 / 100
 262 ms 17752 KB 
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <list>
#include <set>
#include <vector>
#include <string>
#include <math.h>
#include <queue>

#define f first
#define s second
#define sz(a) ((long long)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back

using namespace std;
using ll = long long;

template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is,       pair<T, T2> &p)             { is>>p.f>>p.s;        return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p)             { os<<p.f<<' '<<p.s;   return os; }
template<class T>           inline istream &operator>>(istream &is,       vector<T> &v)               { for (auto &id : v)   is>>id;       return is; }
template<class T>           inline ostream &operator<<(ostream &os, const vector<T> &v)               { for (auto id : v)    os<<id<<'\n';  return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m)              { for (auto id : m)    os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um)   { for (auto id : um)   os<<id<<'\n'; return os; }
template<class T>           inline ostream &operator<<(ostream &os, const list<T> &l)                 { for (auto id : l)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const set<T> &s)                  { for (auto id : s)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const unordered_set<T> &us)       { for (auto id : us)   os<<id<<' ';  return os; }
const long long INF = 1e18;
const bool hasTests = 1;

long long n;
long long w;
vector<pair<long long, long long>> k;
vector<long long> ansWork;

void input() {
    cin >> n >> w;
    k.resize(n);
    cin >> k;
}

void output() {
    cout << ansWork.size() << endl;
    cout << ansWork;
}

void solve() {
    vector<int> perm (n);
    for (int i=0; i<n; i++) {
        perm[i] = i;
    }
    sort(perm.begin(), perm.end(), [&](auto l, auto r) {
        return (float)k[l].f / k[l].s < (float)k[r].f / k[r].s;
    });

    long long ans = 0;
    long long bestWork = 0;
    float bestMoney = 0;

    long long sz = 0;
    long long qu = 0;
    float money = 0;
    float tot = 0;
    priority_queue<long long> curr;

    long long i = 0;
    for (auto temp : perm) {
        auto work = k[temp];
        qu += work.s;
        money = (float)work.f / work.s;
        sz++;
        curr.push(work.s);

        tot = (float)qu * money;
        while (!curr.empty() && tot > w) {
            qu -= curr.top();
            curr.pop();
            tot = (float)qu * money;
            sz--;
        }

        if ((sz > bestWork) || (sz == bestWork && tot < bestMoney)) {
            bestWork = sz;
            bestMoney = tot;
            ans = i; 
        }
        i++;
    }

    qu = 0;
    for (long long i=0; i<=ans; i++) {
        ansWork.push_back(perm[i]);
        qu += k[perm[i]].second;
    }
    money = (float)k[perm[ans]].first / k[perm[ans]].second;

    sort(ansWork.begin(), ansWork.end(), [&](auto l, auto r) {
        return k[l].s < k[r].s;
    });

    tot = (float)money * qu;

    while (tot > w && !ansWork.empty()) {
        tot -= (float)money * k[ansWork.back()].s;
        ansWork.pop_back();
    }

    for (auto& curr : ansWork) {
        curr++;
    }
}

void start() {
    input();
    solve();
    //cout<<"Case #"<<i<<": ";
    output();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    start();
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 6 ms 860 KB Output is correct
15 Correct 6 ms 860 KB Output is correct

Subtask #2
20.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 988 KB Output is correct
5 Correct 19 ms 1884 KB Output is correct
6 Incorrect 149 ms 9252 KB Output isn't correct
7 Incorrect 171 ms 14420 KB Output isn't correct

Subtask #3
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #5
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 3928 KB Output is correct
2 Correct 60 ms 3924 KB Output is correct
3 Incorrect 54 ms 3948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 79 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 254 ms 14672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 262 ms 17752 KB Output isn't correct
2 Halted 0 ms 0 KB -