#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdint>
using namespace std;
bool comp(const vector<int>& a, const vector<int>& b){
int A=0, B=0;
for(int i: a)A+=i;
for(int i: b)B+=i;
return A>B;
}
int main(){
int n, k, c;
scanf("%d%d%d", &n, &k, &c);
vector<vector<int>> people(n, vector<int>(k));
vector<vector<int>> possibilities(k, vector<int>(n));
for(int i=0; i<n; i++)for(int j=0; j<k; j++)
scanf("%d", &people[i][j]), possibilities[j][i]=people[i][j];
for(auto& i: possibilities){
sort(i.begin(), i.end());
i.resize(unique(i.begin(), i.end())-i.begin());
}
vector<vector<int>> combos(1), combos2;
combos.reserve(c*n);
combos2.reserve(c*n);
for(int i=0; i<k; i++){
combos2.clear();
for(auto& l: combos){
for(int j: possibilities[i]){
combos2.push_back(l);
combos2.back().push_back(j);
}
}
swap(combos, combos2);
if(combos.size()>c){
nth_element(combos.begin(), combos.begin()+c, combos.end(), comp);
combos.resize(c);
}
}
sort(combos.rbegin(), combos.rend(), comp);
int last;
while(c>0){
if(combos.empty())
return 0;
auto x=move(combos.back());
combos.pop_back();
last=0;
for(int i: x)
last+=i;
vector<vector<pair<int, int>>> candy(k+1, vector<pair<int, int>>());
int mask=0;
for(int i=n; i--;){
int curr=0;
for(int j=k; j--;){
if(people[i][j]<=x[j]){
if(people[i][j]==x[j])
curr|=1<<j;
}else{
curr=-1;
break;
}
}
if(curr!=-1){
mask|=curr;
for(int j=k; j--;){
if(people[i][j]==x[j])
candy[j+1].emplace_back(curr, i);
}
candy[0].emplace_back(curr, i);
}
}
if(mask+1!=1<<k or candy[0].size()<k)
continue;
vector<vector<int16_t>> team{{0}}, team2;
for(int i=0; i<k; i++){
team2.clear();
for(auto& j: team){
if(j[0]>>i&1){
for(auto l: candy[0]){
if(find(j.begin()+1, j.end(), l.second)==j.end()){
team2.push_back(j);
team2.back().push_back(l.second);
team2.back()[0]|=l.first;
}
}
}else{
for(auto l: candy[1+i]){
if(find(j.begin()+1, j.end(), l.second)==j.end()){
team2.push_back(j);
team2.back().push_back(l.second);
team2.back()[0]|=l.first;
}
}
}
if(team2.size()>=c*720)
break;
}
swap(team, team2);
}
for(auto& i: team)
sort(i.begin()+1, i.end());
sort(team.begin(), team.end());
team.resize(unique(team.begin(), team.end())-team.begin());
c-=team.size();
}
printf("%d\n", last);
}
Compilation message
olympiads.cpp: In function 'int main()':
olympiads.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | if(combos.size()>c){
| ~~~~~~~~~~~~~^~
olympiads.cpp:74:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
74 | if(mask+1!=1<<k or candy[0].size()<k)
| ~~~~~~~~~~~~~~~^~
olympiads.cpp:97:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if(team2.size()>=c*720)
| ~~~~~~~~~~~~^~~~~~~
olympiads.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%d%d", &n, &k, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &people[i][j]), possibilities[j][i]=people[i][j];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
14028 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5708 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
92 ms |
14032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
7876 KB |
Output is correct |
| 2 |
Correct |
53 ms |
7940 KB |
Output is correct |
| 3 |
Correct |
40 ms |
7080 KB |
Output is correct |
| 4 |
Correct |
39 ms |
6724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1287 ms |
171932 KB |
Output is correct |
| 2 |
Correct |
1433 ms |
170556 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
18 ms |
2272 KB |
Output is correct |
| 6 |
Correct |
9 ms |
744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
14028 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5708 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
92 ms |
14032 KB |
Output is correct |
| 5 |
Correct |
58 ms |
7876 KB |
Output is correct |
| 6 |
Correct |
53 ms |
7940 KB |
Output is correct |
| 7 |
Correct |
40 ms |
7080 KB |
Output is correct |
| 8 |
Correct |
39 ms |
6724 KB |
Output is correct |
| 9 |
Correct |
1287 ms |
171932 KB |
Output is correct |
| 10 |
Correct |
1433 ms |
170556 KB |
Output is correct |
| 11 |
Correct |
10 ms |
2252 KB |
Output is correct |
| 12 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 13 |
Correct |
18 ms |
2272 KB |
Output is correct |
| 14 |
Correct |
9 ms |
744 KB |
Output is correct |
| 15 |
Correct |
667 ms |
94544 KB |
Output is correct |
| 16 |
Correct |
585 ms |
94404 KB |
Output is correct |
| 17 |
Correct |
613 ms |
93352 KB |
Output is correct |
| 18 |
Correct |
646 ms |
92888 KB |
Output is correct |
| 19 |
Correct |
1375 ms |
170628 KB |
Output is correct |
