oj.uz

답안 #970972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970972 2024-04-27T16:16:41 Z Bilyana Hiring (IOI09_hiring) C++17
100 / 100
 287 ms 17996 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) {
        if ((float)k[l].f / k[l].s == (float)k[r].f / k[r].s) {
            return k[l].s < k[r].s;
        }
        return (float)k[l].f / k[l].s < (float)k[r].f / k[r].s;
    });
 
    long long ans = 0;
    long long bestWork = 0;
    long long bestMoney2 = 0;
    long long bestMoney = 0;
 
    long long sz = 0;
    long long qu = 0;
    priority_queue<long long> curr;
 
    long long i = 0;
    for (auto temp : perm) {
        auto work = k[temp];
        qu += work.s;
        sz++;
        curr.push(work.s);
 
        while (!curr.empty() && qu * work.f > w * work.s) {
            qu -= curr.top();
            curr.pop();
            sz--;
        }
 
        if ((sz > bestWork) || (sz == bestWork && qu * work.f * bestMoney2 < bestMoney * work.s)) {
            bestWork = sz;
            bestMoney2 = work.s;
            bestMoney = qu * work.f;
            ans = i; 
        }
        i++;
    }
 
    qu = 0;
    for (long long i=0; i<=ans; i++) {
        ansWork.push_back(perm[i]);
        qu += k[perm[i]].second;
    }
    sort(ansWork.begin(), ansWork.end(), [&](auto l, auto r) {
        return k[l].s < k[r].s;
    });
 
    while (k[perm[ans]].first * qu > w * k[perm[ans]].second && !ansWork.empty()) {
        qu -= 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 344 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Correct 6 ms 860 KB Output is correct
15 Correct 6 ms 768 KB Output is correct

Subtask #2
28.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 860 KB Output is correct
5 Correct 20 ms 1884 KB Output is correct
6 Correct 163 ms 9128 KB Output is correct
7 Correct 187 ms 13628 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 3928 KB Output is correct
2 Correct 59 ms 4188 KB Output is correct
3 Correct 59 ms 3924 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 7076 KB Output is correct
2 Correct 87 ms 7000 KB Output is correct
3 Correct 91 ms 6992 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 16412 KB Output is correct
2 Correct 227 ms 15672 KB Output is correct
3 Correct 235 ms 15184 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 16716 KB Output is correct
2 Correct 258 ms 17996 KB Output is correct
3 Correct 287 ms 17800 KB Output is correct