제출 #553607

#제출 시각아이디문제언어결과실행 시간메모리
553607timreizinHiring (IOI09_hiring)C++17
0 / 100
280 ms16332 KiB
#include <iostream> #include <vector> #include <algorithm> #include <deque> #include <set> #include <string> #include <numeric> using namespace std; using ll = long long; struct segtree { int n; vector<ll> sum; vector<int> counter; segtree(int n) : n(n) { sum.resize(4 * n + 5); counter.resize(4 * n + 5); } void update(int p, int l, int r, int v) { if (l > r) return; if (l == r) { sum[v] += p; ++counter[v]; return; } int m = (l + r) >> 1; if (p <= m) update(p, l, m, v << 1); else update(p, m + 1, r, v << 1 | 1); sum[v] = sum[v << 1] + sum[v << 1 | 1]; counter[v] = counter[v << 1] + counter[v << 1 | 1]; } void update(int p) { update(p, 0, n - 1, 1); } //first h such that first h have sum > possible int get(ll w, ll s, int l, int r, int v) { if (l > r || sum[v] * s <= w) return -1; if (l == r) { //c * s > w //c > w / s return w / (s * (sum[v] / counter[v])) + 1; } int m = (l + r) >> 1; if (sum[v << 1] * s > w) return get(w, s, l, m, v << 1); return counter[v << 1] + get(w - sum[v << 1] * s, s, m + 1, r, v << 1 | 1); } int get(ll w, ll s) { return get(w, s, 0, n - 1, 1); } ll getSum(int h, int l, int r, int v) { if (l > r || h == 0) return 0; if (l == r) return h * (sum[v] / counter[v]); int m = (l + r) >> 1; if (counter[v << 1] >= h) return getSum(h, l, m, v << 1); else return sum[v << 1] + getSum(h - counter[v << 1], m + 1, r, v << 1 | 1); } ll getSum(int h) { return getSum(h, 0, n - 1, 1); } }; struct best { int i; int h; ll n, d; best(int i, int h, ll n, ll d) : i(i), h(h), n(n), d(d) {} friend bool operator<(best b, best a) { if (b.h < a.h) return true; if (b.h > a.h) return false; return b.n * a.d < b.d * a.n; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n; ll w; cin >> n >> w; vector<ll> s(n), q(n); for (int i = 0; i < n; ++i) cin >> s[i] >> q[i]; vector<int> inds(n); iota(inds.begin(), inds.end(), 0); sort(inds.begin(), inds.end(), [&s, &q](int i, int j){ return s[i] * q[j] < s[j] * q[i]; }); best res{0, 0, 0, 1}; segtree ds(20001); for (int i = 0; i < inds.size(); ++i) { ds.update(q[inds[i]]); int h = ds.get(w * q[inds[i]], s[inds[i]]); if (h == -1) h = i + 2; --h; ll sum = ds.getSum(h); res = max(res, {i, h, sum * s[inds[i]], q[inds[i]]}); } cout << res.h; return 0; } /* 4 100 5 1000 10 100 8 10 20 1 */ /* 3 4 1 2 1 3 1 3 */ /* 3 40 10 1 10 2 10 3 */

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp: In function 'int main()':
hiring.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < inds.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...