AtCoder Beginner Contest 034 D - 食塩水
問題
D: 食塩水 - AtCoder Beginner Contest 034 | AtCoder
↑入力形式のNとKが入れ替わっている(引っかかった)
解法
winjii.hatenablog.com
解法自体はSkiと同じ。
平均最大化。二分探索でDPできるようにする。
実装
Skiの時も思ったけど、目指す平均を固定することでDPが出来るようになるのは不思議
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 30; int N, D; struct Treasure { int x, y; Treasure() { x = y = 0; } Treasure(int _x, int _y) { x = _x; y = _y; } Treasure operator + (const Treasure &t) const { return Treasure(x + t.x, y + t.y); } Treasure operator - (const Treasure &t) const { return Treasure(x - t.x, y - t.y); } bool operator < (const Treasure &d) const { return x < d.x; } }; Treasure treasure[MAX_N]; void DFS(int l, int r, Treasure sum, vector<Treasure> &res) { if (l == r) { res.push_back(sum); return; } DFS(l + 1, r, sum, res); DFS(l + 1, r, sum + treasure[l], res); DFS(l + 1, r, sum - treasure[l], res); } int sum[20000000]; signed main() { cin >> N >> D; for (int i = 0; i < N; i++) { cin >> treasure[i].x >> treasure[i].y; } vector<Treasure> s, t; s.reserve(20000000); t.reserve(20000000); DFS(0, N / 2, Treasure(), s); DFS(N / 2, N, Treasure(), t); sort(s.begin(), s.end()); sort(t.begin(), t.end()); int ans = -LLONG_MAX; { int l = 0, r = 0; deque<int> dq; for (int i = t.size() - 1; i >= 0; i--) { while (r < s.size() && s[r].x + t[i].x <= D) { while (!dq.empty() && s[dq.back()].y <= s[r].y) dq.pop_back(); dq.push_back(r); r++; } while (l < s.size() && s[l].x + t[i].x < -D) { if (!dq.empty() && dq.front() == l) dq.pop_front(); l++; } if (!dq.empty()) ans = max(ans, t[i].y + s[dq.front()].y); } } printf("%lld\n", ans); return 0; }