Submission #1673701

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

#define INF 10000000

using namespace std;

int N, M, P, Q, R;
bool use_p[20];
int x[400], y[400], z[400];

int search(int index, int use_num){
	
	int ret = 0;
	
	if(N - index + use_num < P){
		return 0;
	}
	
	if(index == N){
		int sum[20] = {};
		for(int i = 0; i < R; i++){
			if(use_p[x[i]]){
				sum[y[i]] -= z[i];
			}
		}
		sort(sum, sum + M);
		for(int i = 0; i < Q; i++){
			ret -= sum[i];
		}
		return ret;
	}
	if(use_num == P){
		use_p[index] = false;
		ret = max(ret, search(index + 1, use_num));
	}else{
		use_p[index] = false;
		ret = max(ret, search(index + 1, use_num));
		use_p[index] = true;
		ret = max(ret, search(index + 1, use_num + 1));
	}
}

int main(){
	
	cin >> N >> M >> P >> Q >> R;
	
	for(int i = 0; i < R; i++){
		cin >> x[i] >> y[i] >> z[i];
		x[i]--;
		y[i]--;
	}
	
	cout << search(0, 0) << endl;
	
	return 0;
}

Submission Info

Judge Result