Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct Person {
- int id;
- long long audience_strength;
- vector<long long> player_strengths;
- };
- bool comparePeople(const Person& a, const Person& b) {
- return a.audience_strength > b.audience_strength;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int n, p, k;
- cin >> n >> p >> k;
- vector<Person> people(n);
- for (int i = 0; i < n; ++i) {
- people[i].id = i;
- cin >> people[i].audience_strength;
- }
- for (int i = 0; i < n; ++i) {
- people[i].player_strengths.resize(p);
- for (int j = 0; j < p; ++j) {
- cin >> people[i].player_strengths[j];
- }
- }
- sort(people.begin(), people.end(), comparePeople);
- vector<vector<long long>> dp(n + 1, vector<long long>(1 << p, -1));
- dp[0][0] = 0;
- for (int i = 1; i <= n; ++i) {
- for (int mask = 0; mask < (1 << p); ++mask) {
- // the number of players
- int num_players_in_mask = 0;
- for(int j=0; j<p; ++j){
- if((mask >> j) & 1){
- num_players_in_mask++;
- }
- }
- // what if people i-1 is audience
- long long non_player_strength = -1;
- if (dp[i - 1][mask] != -1) {
- int audience_candidates = i - num_players_in_mask;
- non_player_strength = dp[i - 1][mask];
- if (audience_candidates <= k)
- non_player_strength = dp[i - 1][mask] + people[i - 1].audience_strength;
- }
- dp[i][mask] = non_player_strength;
- // what if people i-1 is player
- for (int j = 0; j < p; ++j) {
- if ((mask >> j) & 1) {
- int prev_mask = mask ^ (1 << j);
- if (dp[i - 1][prev_mask] != -1) {
- long long player_strength = dp[i - 1][prev_mask] + people[i - 1].player_strengths[j];
- dp[i][mask] = max(dp[i][mask], player_strength);
- }
- }
- }
- }
- }
- cout << dp[n][(1 << p) - 1] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
