| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 785718 | canadavid1 | Hiring (IOI09_hiring) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define all(x) begin(x),end(x)
#define rep(var,e) for(int var = 0; var < e; var++)
struct Rational
{
int num;
int den;
Rational() {}
Rational(int n, int d=1) : num(n), den(d) {}
Rational operator*(Rational other) {return Rational(num*other.num,den*other.den);}
Rational inv() {return Rational(den,num);}
Rational operator/(Rational other) {return *this * (other.inv());}
Rational operator+(Rational other) {return Rational(num*other.den + other.num * den,den*other.den);}
Rational neg() {return Rational(-num,den);}
Rational operator-(Rational other) {return *this + (other.neg());}
Rational operator+=(Rational other) {*this = *this + other;return *this;}
Rational simplify()
{
int a = gcd(num,den);
if(den < 0) a = -a;
num /= a;
den /= a;
return *this;
}
const bool operator<(const Rational& other) const
{
return num * other.den < other.num * den;
}
const bool operator>(const Rational& other) const
{
return other < *this;
}
};
struct worker
{
int mincost,skill,num;
const bool operator<(const worker& other) const
{
return skill < other.skill;
}
};
signed main()
{
int N,W;
cin >> N >> W;
vector<worker> workers(N);
rep(i,N)
{
cin >> workers[i].mincost >> workers[i].skill;
workers[i].num = i+1;
}
// one of the included workers is paid their minimum
// for each, add the cheapest workers until can't anymore
// sort all workers by min_cost
sort(all(workers));
vector<int> included_workers;
Rational p(0);
rep(i,N) // index in workers
{
worker& s = workers[i];
Rational costperskill = Rational(s.mincost,s.skill).simplify();
Rational cc = 0;
vector<int> included;
for(auto & j : workers)
{
Rational pay = costperskill * j.skill;
if(pay + cc > W) break;
if(pay < j.mincost) continue;
included.push_back(j.num);
cc += pay;
}
if (included.size() > included_workers.size()
|| included.size() == included_workers.size() && cc < p)
{
swap(included,included_workers); // O(1) assign, unneccesary
p = cc;
continue;
}
}
cout << included_workers.size() << "\n";
for(auto i : included_workers) cout << i << "\n";
}