#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;
const ll inf=1e9;
struct team{
vll v;
ll n, id;
void init(ll tn){
n=tn;
v=vll(n, -inf);
}
void rd(ll tn){
n=tn;
v.resize(n);
for(ll i=0;i<n;i++){
cin>>v[i];
}
}
void mxwith(vll &cur){
for(ll i=0;i<n;i++){
cur[i]=max(cur[i], v[i]);
}
}
void operator=(const team &tar){
for(ll i=0;i<n;i++){
v[i]=tar.v[i];
}
id=tar.id;
}
bool operator<(const team &tar) const{
return id<tar.id;
}
};
const ll mxN=505;
ll n, k, c;
vll a[mxN];
vector<pll> v[6];
bool use[mxN];
ll gt(vector<team> &tar, vll &cur){
for(ll i=0;i<k;i++){
tar[i].mxwith(cur);
}
ll re=0;
for(ll i=0;i<k;i++){
re+=cur[i];
}
return re;
}
ll gt2(vll &tar){
ll re=0;
for(ll i=0;i<k;i++){
ll cur=0;
for(ll j=0;j<k;j++){
cur=max(cur, a[j][i]);
}
re+=cur;
}
return re;
}
void solve(){
memset(use, 0, sizeof(use));
cin>>n>>k>>c;
for(ll i=0;i<k;i++){
v[i].resize(n);
}
for(ll i=0;i<n;i++){
a[i].resize(k);
for(ll j=0;j<k;j++){
cin>>v[j][i].F;
v[j][i].S=i;
a[i][j]=v[j][i].F;
}
}
for(ll i=0;i<k;i++){
sort(v[i].begin(), v[i].end(), greater<pll>());
}
set<ll> in;
ll mx=0;
for(ll i=0;i<k;i++){
in.insert(v[i][0].S);
mx+=v[i][0].F;
use[v[i][0].S]=1;
}
while((ll)in.size()<k){
for(ll i=0;i<n;i++){
if(!use[i]){
in.insert(i);
use[i]=1;
break;
}
}
}
priority_queue<pair<ll, set<ll>>> pq;
map<set<ll>, bool> done;
//cout<<'\n';
//cout<<re<<'\n';
pq.push({mx, in});
done[in]=1;
ll ans;
//cout<<mx<<'\n';
//assert(1);
//bool b=0;
for(ll i=0;i<c && !pq.empty();i++){
pair<ll, set<ll>> now=pq.top(); pq.pop();
ans=now.F;
set<ll> tep=now.S;
memset(use, 0, sizeof(use));
for(auto it:tep){
use[it]=1;
}
for(auto it:tep){
set<ll> nxt;
for(auto it2:tep){
if(it2==it) continue;
//assert(tep[j]<n);
/*if(tep[j]>=n){
cout<<"bad "<<i<<'\n';
for(auto it:tep){
cout<<it<<' ';
}
cout<<'\n';
b=1;
break;
}*/
nxt.insert(it2);
}
//if(b) break;
vll cur(k, -inf);
for(auto it3:nxt){
for(ll j=0;j<k;j++){
cur[j]=max(cur[j], a[it3][j]);
}
}
for(ll j=0;j<n;j++){
if(!use[j]){
nxt.insert(j);
if(done[nxt]){
nxt.erase(j);
}
else{
done[nxt]=1;
vll cur2=cur;
for(ll ii=0;ii<k;ii++){
cur2[ii]=max(cur2[ii], a[j][ii]);
}
ll re=0;
for(ll ii=0;ii<k;ii++){
re+=cur2[ii];
}
pq.push({re, nxt});
nxt.erase(j);
}
//done.insert(hs(nxt));
}
}
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
olympiads.cpp: In function 'void solve()':
olympiads.cpp:176:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
176 | cout<<ans<<'\n';
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
507 ms |
42516 KB |
Output is correct |
2 |
Correct |
587 ms |
41960 KB |
Output is correct |
3 |
Correct |
529 ms |
42228 KB |
Output is correct |
4 |
Correct |
388 ms |
10272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
394 ms |
65592 KB |
Output is correct |
2 |
Correct |
346 ms |
55856 KB |
Output is correct |
3 |
Correct |
440 ms |
63072 KB |
Output is correct |
4 |
Correct |
386 ms |
57880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
801 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
507 ms |
42516 KB |
Output is correct |
2 |
Correct |
587 ms |
41960 KB |
Output is correct |
3 |
Correct |
529 ms |
42228 KB |
Output is correct |
4 |
Correct |
388 ms |
10272 KB |
Output is correct |
5 |
Correct |
394 ms |
65592 KB |
Output is correct |
6 |
Correct |
346 ms |
55856 KB |
Output is correct |
7 |
Correct |
440 ms |
63072 KB |
Output is correct |
8 |
Correct |
386 ms |
57880 KB |
Output is correct |
9 |
Runtime error |
801 ms |
262144 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |