#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 503, inf = 1e9;
int mx[len], mine[len], who[len], score[10];
int par[len][len], sum[len][len], dp[len][10], best[len][10];
int n, k, c;
struct node{
int opt;
bitset<len> block, must;
vector<int> extra; /// check what happens here
node(bitset<len> bl, bitset<len> mu){
block = bl;
must = mu;
/// assume that bl, mu are always valid sets
// inits
int rem = k-must.count();
for (int j = 0; j < k; j++)
score[j] = 0;
for (int bit = 1; bit < (1<<k); bit++)
mx[bit] = -inf, mine[bit] = 0;
for (int i = 0; i < n; i++)
if (must[i])
for (int j = 0; j < k; j++)
score[j] = max(score[j], par[i][j]);
for (int bit = 1; bit < (1<<k); bit++)
for (int j = 0; j < k; j++)
if (bit&(1<<j))
mine[bit] += score[j];
for (int i = 0; i < n; i++){
if (block[i]|must[i]) continue;
for (int bit = 1; bit < (1<<k); bit++)
if (sum[i][bit] > mx[bit])
mx[bit] = sum[i][bit], who[bit] = i;
}
// compute dp
for (int bit = 1; bit < (1<<k); bit++){
dp[bit][0] = -inf;
for (int i = 1; i <= rem; i++){
dp[bit][i] = -inf;
for (int sub = bit; sub > 0; sub = (sub-1)&bit)
if (dp[bit-sub][i-1] != -inf && dp[bit-sub][i-1]+mx[sub] > dp[bit][i])
dp[bit][i] = dp[bit-sub][i-1]+mx[sub], best[bit][i] = sub;
}
}
// find opt answer
int cur = 0;
for (int bit = 1; bit < (1<<k); bit++)
if (dp[bit][rem]+mine[((1<<k)-1)-bit] > dp[cur][rem]+mine[((1<<k)-1)-cur])
cur = bit;
opt = dp[cur][rem]+mine[((1<<k)-1)-cur];
// reconstruct useful team members
while (cur > 0){
extra.pb(who[best[cur][rem]]);
cur -= best[cur][rem];
rem--;
}
// add useless members
sort(extra.begin(), extra.end());
/*printf("mem now:");
for (int j = 0; j < extra.size(); j++)
printf(" %d", extra[j]);
printf("\n");*/
for (int i = n-1, j = (int)extra.size()-1; i >= 0 && rem; i--){
while (j > 0 && extra[j] > i)
j--;
if ((j < 0 || i != extra[j]) && !block[i] && !must[i])
extra.pb(i), rem--;
}
}
bool operator<(const node &a) const{
return (opt < a.opt);
}
void print(){
printf("opt = %d\n", opt);
printf("blocked:");
for (int i = 0; i < n; i++)
if (block[i])
printf(" %d", i);
printf("\n");
printf("must:");
for (int i = 0; i < n; i++)
if (must[i])
printf(" %d", i);
printf("\n");
printf("extra:");
for (int i = 0; i < extra.size(); i++)
printf(" %d", extra[i]);
printf("\n");
}
};
priority_queue<node> pq;
int main(){
scanf("%d %d %d", &n, &k, &c);
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
scanf("%d", &par[i][j]);
for (int i = 0; i < n; i++)
for (int bit = 0; bit < (1<<k); bit++)
for (int j = 0; j < k; j++)
if (bit&(1<<j))
sum[i][bit] += par[i][j];
int ans;
bitset<len> block, must;
pq.push(node(block, must));
while (!pq.empty()){
node u = pq.top();
pq.pop();
c--;
//printf("c = %d, node u =\n", c);
//u.print();
if (c == 0){
ans = u.opt;
break;
}
block = u.block;
must = u.must;
for (int j = 0; j < u.extra.size(); j++){
//printf("extra = %d\n", u.extra[j]);
block[u.extra[j]] = 1;
if (n-block.count() >= k){
node v = node(block, must);
//v.print();
pq.push(v);
}
//printf("pushed\n");
block[u.extra[j]] = 0;
must[u.extra[j]] = 1;
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
olympiads.cpp: In member function 'void node::print()':
olympiads.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < extra.size(); i++)
~~^~~~~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:144:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < u.extra.size(); j++){
~~^~~~~~~~~~~~~~~~
olympiads.cpp:147:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (n-block.count() >= k){
~~~~~~~~~~~~~~~~^~~~
olympiads.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &k, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &par[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2296 KB |
Output is correct |
| 4 |
Correct |
10 ms |
2296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
632 KB |
Output is correct |
| 2 |
Correct |
11 ms |
504 KB |
Output is correct |
| 3 |
Correct |
16 ms |
632 KB |
Output is correct |
| 4 |
Correct |
14 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
58 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
141 ms |
2756 KB |
Output is correct |
| 4 |
Correct |
185 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
78 ms |
2584 KB |
Output is correct |
| 6 |
Correct |
10 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2296 KB |
Output is correct |
| 4 |
Correct |
10 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
14 ms |
632 KB |
Output is correct |
| 6 |
Correct |
11 ms |
504 KB |
Output is correct |
| 7 |
Correct |
16 ms |
632 KB |
Output is correct |
| 8 |
Correct |
14 ms |
632 KB |
Output is correct |
| 9 |
Correct |
65 ms |
2296 KB |
Output is correct |
| 10 |
Correct |
58 ms |
2296 KB |
Output is correct |
| 11 |
Correct |
141 ms |
2756 KB |
Output is correct |
| 12 |
Correct |
185 ms |
3160 KB |
Output is correct |
| 13 |
Correct |
78 ms |
2584 KB |
Output is correct |
| 14 |
Correct |
10 ms |
504 KB |
Output is correct |
| 15 |
Correct |
152 ms |
2792 KB |
Output is correct |
| 16 |
Correct |
66 ms |
2424 KB |
Output is correct |
| 17 |
Correct |
79 ms |
2296 KB |
Output is correct |
| 18 |
Correct |
102 ms |
2436 KB |
Output is correct |
| 19 |
Correct |
58 ms |
2296 KB |
Output is correct |
