ABC018 D - バレンタインデー
問題
考察
部分点解法
$ {}_NC_P \times {}_MC_Q
満点解法
女子側を固定すると、どの男子を入れればどれだけの幸福度が上がるかは$ O(R)で計算できる。それがわかっていれば、幸福度が大きく上がる順に$ Q人を選ぶ貪欲法で幸福度が最大化できる。 このとき計算量は$ O({}_NC_P \times R \log R )
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int first_fixed_size_subset(int n, int k) { return (1 << k) - 1; }
int next_fixed_size_subset(int n, int k, int& s) {
int x = s & -s, y = s + x;
s = (((s & ~y) / x) >> 1) | y;
if (s >= (1 << n)) return 0;
return s;
}
struct Choco {
int from, to, happiness;
};
int main() {
int N, M, P, Q, R;
cin >> N >> M >> P >> Q >> R;
vector<Choco> C(R);
rep(i, R) {
cin >> Ci.from >> Ci.to >> Ci.happiness; }
ll ans = 0;
int sp = first_fixed_size_subset(N, P);
do {
vector<int> s(M, 0);
rep(i, R) {
if ((sp >> Ci.from) & 1) s[Ci.to] += Ci.happiness; }
sort(s.rbegin(), s.rend());
ans = max(ans, accumulate(s.begin(), s.begin() + Q, 0LL));
} while (next_fixed_size_subset(N, P, sp));
cout << ans << endl;
return 0;
}