Submission #388196

#	Time	Username	Problem	Language	Result	Execution time	Memory
388196		leaked	Olympiads (BOI19_olympiads)	C++14	0 / 100	2090 ms	262148 KiB

olympiads

#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;
    }
//    int calc(){}
};
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]));
    auto calc=[&](vec<int> &vc){
        int s=0;
        for(int i=0;i<m;i++){
            int mx=0;
            for(int j=0;j<m;j++) mx=max(mx,a[hah[j][vc[j]].s][i]);
            s+=mx;
        }
        return s;
    };
    priority_queue<buben>pq;
    map<ull,bool>mp;
    map<vec<int>,bool>mp2;
    vec<int>lol(m,0);
    buben me(0,lol);
    me.sum=calc(me.vc);
    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;
        bool ok=1;
        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;
            }else ok=0;
        }
        if(mp.count(hs)==0){
            mp[hs]=1;
            if(ok){
                k--;
                if(k==0){
                    cout<<c.sum<<endl;
                    return 0;
                }
            }
        }
        buben nw=c;
        for(int i=0;i<m;i++){
            nw.sum=c.sum;
            nw.vc[i]++;
            if(nw.vc[i]!=n){
                nw.sum=calc(nw.vc);
                pq.push(nw);
            }
            nw.vc[i]=c.vc[i];
        }
//        cerr<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32