This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 long long ll;
const ll A=9828401843;
const ll B=1e9+78328738;
const ll inf=1e17;
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;
vector<team> a;
vector<team> on;
vector<team> best;
bool use[mxN];
unordered_map<ll, ll> done;
ll hs(const vll &tar){
ll re=0;
vll tep=tar;
sort(tep.begin(), tep.end());
for(ll i=0;i<k;i++){
re=(re*A+tep[i])%B;
}
return re;
}
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[tar[j]].v[i]);
}
re+=cur;
}
return re;
}
void solve(){
memset(use, 0, sizeof(use));
cin>>n>>k>>c;
a.resize(n);
for(ll i=0;i<k;i++){
team tep;
tep.init(k);
best.pb(tep);
}
for(ll i=0;i<n;i++){
a[i].rd(k);
a[i].id=i;
}
for(ll i=0;i<n;i++){
for(ll j=0;j<k;j++){
if(a[i].v[j]>best[j].v[j]){
best[j]=a[i];
}
}
}
ll cnt=0;
vector<team> be;
for(ll i=0;i<k;i++){
if(use[best[i].id]){
cnt++;
}
else{
use[best[i].id]=1;
be.pb(best[i]);
}
}
while(cnt--){
for(ll i=0;i<n;i++){
if(!use[i]){
be.pb(a[i]);
use[i]=1;
break;
}
}
}
priority_queue<pair<ll, vll>> pq;
vll cur(k, -inf);
ll re=gt(be, cur);
vll tep;
for(ll i=0;i<n;i++){
if(use[i]){
tep.pb(i);
//cout<<i<<' ';
}
}
//cout<<'\n';
//cout<<re<<'\n';
pq.push({re, tep});
done[hs(tep)]++;
ll ans;
//assert(1);
//bool b=0;
vll cur2;
for(ll i=0;i<c && !pq.empty();i++){
pair<ll, vll> now=pq.top(); pq.pop();
ans=now.F;
tep=now.S;
memset(use, 0, sizeof(use));
for(ll j=0;j<k;j++){
use[tep[j]]=1;
}
for(ll pos=0;pos<k;pos++){
vll nxt;
for(ll j=0;j<k;j++){
if(j==pos) 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.pb(tep[j]);
}
//if(b) break;
for(ll j=0;j<n;j++){
if(!use[j]){
for(ll ii=0;ii<k;ii++){
cur[ii]=-inf;
}
for(auto it:nxt){
for(ll j=0;j<k;j++){
cur[j]=max(cur[j], a[it].v[j]);
}
}
nxt.pb(j);
ll h=hs(nxt);
if(done[h]){
nxt.pop_back();
}
else{
done[h]++;
for(ll ii=0;ii<k;ii++){
cur[ii]=max(cur[ii], a[j].v[ii]);
}
ll re=0;
for(ll ii=0;ii<k;ii++){
re+=cur[ii];
}
pq.push({re, nxt});
nxt.pop_back();
}
//done.insert(hs(nxt));
}
}
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |