oj.uz

답안 #220795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220795 2020-04-08T21:07:30 Z tatyam Hiring (IOI09_hiring) C++17
100 / 100
 348 ms 26892 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)


ll cnt;
vector<ll> hist;
struct Q{
    priority_queue<pll> q;
    ll sum = 0;
    void push(ll val, ll index){
        cnt++;
        sum += val;
        hist.push_back(index);
        q.emplace(val, index);
    }
    void pop(){
        cnt--;
        sum -= q.top().first;
        hist.push_back(q.top().second);
        q.pop();
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, w;
    cin >> n >> w;
    vector<pll> a(n);
    each(i, a) cin >> i.first >> i.second;
    vector<ll> b(n);
    iota(all(b), 0);
    sort(all(b), [&](ll x, ll y){ return a[x].first * a[y].second < a[x].second * a[y].first; });
    ld rate = 0, cost = 0;
    ll ans = 0;
    Q q;
    vector<bool> hire(n);
    auto update = [&](ld cost_) -> void {
        if(ans > cnt) return;
        if(ans == cnt && cost <= cost_) return;
        ans = cnt;
        cost = cost_;
        each(i, hist) hire[i] = !hire[i];
        hist.clear();
    };
    each(i, b){
        auto [sal, qual] = a[i];
        rate = ld(sal) / qual;
        q.push(qual, i);
        while(q.sum * rate > w) q.pop();
        update(q.sum * rate);
    }
    cout << ans << '\n';
    rep(n) if(hire[i]) cout << i + 1 << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 7 ms 696 KB Output is correct
10 Correct 7 ms 684 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 8 ms 896 KB Output is correct
14 Correct 11 ms 1152 KB Output is correct
15 Correct 11 ms 1280 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 436 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 16 ms 1660 KB Output is correct
5 Correct 33 ms 3824 KB Output is correct
6 Correct 187 ms 16484 KB Output is correct
7 Correct 284 ms 22368 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

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

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 9840 KB Output is correct
2 Correct 107 ms 9968 KB Output is correct
3 Correct 136 ms 9968 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 22624 KB Output is correct
2 Correct 320 ms 22748 KB Output is correct
3 Correct 302 ms 22624 KB Output is correct

Subtask #9
6.0 / 6.0

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