Submission #1354437

#TimeUsernameProblemLanguageResultExecution timeMemory
1354437WarinchaiOlympiads (BOI19_olympiads)C++20
0 / 100
2093 ms327680 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<int,int>>pos[10];
int rv[10][500];
int val[10][505];
int n,k,c;

struct info{
    int cost;
    int p[7];
    info(){
        for(int i=1;i<=k;i++)p[i]=1;
        cost=g();
    }
    friend bool operator<(info a,info b){
        return a.cost<b.cost;
    }
    int g(){
        int ans=0;
        int ar[8]={};
        for(int i=1;i<=k;i++){
            for(int j=1;j<=k;j++){
                int temp=pos[j][p[j]-1].second;
                ar[i]=max(ar[i],val[i][temp]);
            }
        }
        for(int i=1;i<=k;i++)ans+=ar[i];
        return ans;
    }
};
int cnt[50005];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            int x;cin>>x;
            val[j][i]=x;
            pos[j].push_back({x,i});
        }
    }
    for(int i=1;i<=k;i++){
        sort(pos[i].begin(),pos[i].end());
        reverse(pos[i].begin(),pos[i].end());
    }
    info st=info();
    priority_queue<info>pq;
    pq.push(st);
    int cur=0;
    int ans=0;
    //cerr<<"work\n";
    map<vector<int>,int>mp;
    while(!pq.empty()&&cur<c){
        auto x=pq.top();
        pq.pop();
        //cerr<<"x:"<<x.cost<<" ";
        //for(int i=1;i<=k;i++)cerr<<pos[i][x.p[i]-1].second<<' ';
        //cerr<<"\n";
        ans=x.cost;
        int can=1;
        for(int i=1;i<=k;i++){
            cnt[pos[i][x.p[i]-1].second]++;
            if(cnt[pos[i][x.p[i]-1].second]>1)can=0;
        }
        for(int i=1;i<=k;i++){
            cnt[pos[i][x.p[i]-1].second]--;
        }
        vector<int>temp;
        for(int i=1;i<=k;i++){
            temp.push_back(pos[i][x.p[i]-1].second);
        }
        sort(temp.begin(),temp.end());
        if(mp[temp])can=0;
        else mp[temp]=1;
        cur+=can;
        //cerr<<"work\n";
        for(int i=1;i<=k;i++){
            //cerr<<"i:"<<i<<'\n';
            auto temp=x;
            //cerr<<"ii:"<<temp.p[i]<<'\n';
            if(temp.p[i]<n){
                temp.p[i]++;
                temp.cost=temp.g();
                pq.push(temp);
            }
        }
    }
    cout<<ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...