#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e9 + 7;
int a[505][10];
int n, k, c;
struct info{
vector<int> idx;
int ans;
info(){}
info(vector<int> _idx, int _ans) : idx(_idx), ans(_ans){}
bool operator < (const info& other) const{
return ans > other.ans;
}
};
set<info> q;
set<set<int>> used;
int cal(set<int> id){
vector<int> mx(k);
for(auto x : id){
for(int i = 0; i < k; i++){
mx[i] = max(mx[i], a[x][i]);
}
}
return accumulate(mx.begin(), mx.end(), 0);
}
set<int> to_set(vector<int> a){
set<int> st;
for(auto x : a) st.insert(x);
return st;
}
vector<int> to_vector(set<int> st){
vector<int> a;
for(auto x : st) a.pb(x);
return a;
}
signed main(void){
fastio;
cin>>n>>k>>c;
vector<int> mx(k);
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
cin>>a[i][j];
if(a[i][j] > a[mx[j]][j]) mx[j] = i;
}
}
// cout<<"ok\n";
set<int> st;
for(int i = 0; i < k; i++) st.insert(mx[i]);
for(int i = 0; i < n; i++){
if(st.size() == k) break;
if(st.count(i)) continue;
st.insert(i);
}
used.insert(st);
q.insert(info(to_vector(st), cal(st)));
int push = 1;
for(int rd = 0; rd < c; rd++){
auto [idx, ans] = *q.begin(); q.erase(q.begin());
while(q.size() >= c) q.erase(--q.end());
if(rd == c - 1){
cout<<ans<<"\n";
return 0;
}
for(auto x : idx){
if(push > 5e5) break;
set<int> cur;
for(auto u : idx){
if(u != x) cur.insert(u);
}
for(int j = 0; j < n; j++){
if(!cur.count(j)){
cur.insert(j);
if(!used.count(cur)){
push++;
q.insert(info(to_vector(cur), cal(cur)));
used.insert(cur);
}
cur.erase(j);
}
}
}
}
}
Compilation message
olympiads.cpp: In function 'int main()':
olympiads.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | if(st.size() == k) break;
| ~~~~~~~~~~^~~~
olympiads.cpp:70:24: warning: comparison of integer expressions of different signedness: 'std::set<info>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | while(q.size() >= c) q.erase(--q.end());
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
11216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
573 ms |
54356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3133 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
11216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
