Submission #388182

#TimeUsernameProblemLanguageResultExecution timeMemory
388182leakedOlympiads (BOI19_olympiads)C++14
0 / 100
136 ms262148 KiB
#include <bits/stdc++.h>
//#pra
#define sz(x) (int)x.size()
#define vec vector
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int N=3e2+3;
typedef unsigned long long ull;
auto rnd=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
ull r[N];
struct buben{
    int sum;
    vec<int>vc;
    buben();
    buben(int _a,vec<int> _vc) : sum(_a),vc(_vc) {}
    const bool operator<(const buben &o) const{
        if(o.sum!=sum) return sum<o.sum;
        return true;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    /// i suppose it's n*m*k*log
    vec<vec<int>>a(n,vec<int>(m));
    vec<vec<pii>>hah(m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            hah[j].pb({a[i][j],i});
        }
    }
    for(int i=0;i<m;i++) sort(rall(hah[i]));
    priority_queue<buben>pq;
    map<ull,bool>mp;
    map<vec<int>,bool>mp2;
    vec<int>lol(m,0);
    buben me(0,lol);
    for(int j=0;j<m;j++) me.sum+=hah[j][me.vc[j]].f;
    pq.push(me);
    vec<int>used(n,0);
    int cr=0;
    for(int i=0;i<n;i++) r[i]=rnd();
    while(!pq.empty()){
//        cerr<<c.sum<<endl;
        auto c=pq.top();pq.pop();
//        cerr<<c.sum<<endl;
        if(mp2.count(c.vc)) continue;
//        cerr<<c.sum<<endl;
        cr++;
        mp2[c.vc]=1;
        ull hs=0;
        for(int j=0;j<m;j++) {
            if(used[hah[j][c.vc[j]].s]!=cr){
                hs+=r[hah[j][c.vc[j]].s];
                used[hah[j][c.vc[j]].s]=cr;
            }
        }
        if(mp.count(hs)==0){
            mp[hs]=1;
//            cerr<<c.sum<<endl;
//            for(int j=0;j<m;j++) cerr<<hah[j][c.vc[j]].s+1<<' ';
//            cerr<<endl;
            k--;
            if(k==0){
                cout<<c.sum<<endl;
                return 0;
            }
        }
        buben nw=c;
        for(int i=0;i<k;i++){
            nw.sum-=hah[i][nw.vc[i]].f;
            nw.vc[i]++;
            if(nw.vc[i]!=n){
                int mx=0;
                for(int j=0;j<k;j++){
                    mx=max(mx,a[hah[j][nw.vc[j]].s][i]);
                }
                nw.sum+=mx;
                pq.push(nw);
                nw.sum-=mx;
            }
            nw.vc[i]--;
            nw.sum+=hah[i][nw.vc[i]].f;
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...