AtCoder Beginner Contest 018 D: バレンタインデー

問題

abc018.contest.atcoder.jp

解法

またはなら間に合うが、は間に合わない。そこで男子か女子のどちらか一方だけをビットで回して、もう一方は相手のビットに対する得点を出してソートし、良い方から順にグループに入れれば良い。

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int P = sc.nextInt();
		int Q = sc.nextInt();
		int R = sc.nextInt();
		ArrayList<ArrayList<Integer[]>> choco = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			choco.add(new ArrayList<Integer[]>());
		}

		for (int i = 0; i < R; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			int z = sc.nextInt();
			choco.get(x).add(new Integer[] { y, z });
		}

		int max = 0;
		for (int bit = 0; bit < (1 << N); bit++) {
			if (Integer.bitCount(bit) != P) {
				continue;
			}
			int[] zs = new int[M];
			for (int n = 0; n < N; n++) {
				if (((bit >> n) & 1) == 1) {
					for (Integer[] c : choco.get(n)) {
						zs[c[0]] += c[1];
					}
				}
			}
			Arrays.sort(zs);
			int sum = 0;
			for (int i = 0; i < Q; i++) {
				sum += zs[M - 1 - i];
			}
			max = Math.max(max, sum);
		}
		System.out.println(max);

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}