Submission #1370629

#TimeUsernameProblemLanguageResultExecution timeMemory
1370629eradaxOlympiads (BOI19_olympiads)C++20
100 / 100
30 ms10896 KiB
#include<bits/stdc++.h>
using namespace std;

struct S {
    int s,c;
    vector<int> b, u, m;
    S(int n, int k):s(0),c(0),b(n),u(k,-1),m(k){}

    bool operator<(const S& o) const { return s<o.s; }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k,c;cin>>n>>k>>c;c--;
    vector<vector<int>> a(n,vector<int>(k));
    for(auto&i:a)for(int&j:i)cin>>j;

    priority_queue<S> pq;
    {
        S start(n,k);
        for(int i=start.c;i<k;i++) {
            int ind=-1;
            for(int j=0;j<n;j++) if(!start.b[j]&&(ind<0||a[ind][i]<a[j][i]))ind=j;
            start.u[i]=ind;
            start.b[ind]=1;
        }
        for(int j=0;j<k;j++)for(int ind:start.u)start.m[j]=max(start.m[j],a[ind][j]);
        start.s=accumulate(begin(start.m),end(start.m),0);
        pq.push(start);
    }

    while(c--) {
        auto team=pq.top();
        pq.pop();

        for(int i=team.c;i<k;i++){
            int f=0;
            S nxt = team;
            for(int j=0;j<i;j++)nxt.b[team.u[j]]=2;
            nxt.b[team.u[i]]=3;
            for(int&j:nxt.b)if(j==1)j=0;
            nxt.m.assign(k,0);
            nxt.s=0;
            nxt.c=i;

            for(int j=nxt.c;j<k;j++) {
                int ind=-1;
                for(int l=0;l<n;l++)if(!nxt.b[l]&&(ind<0||a[ind][j]<a[l][j]))ind=l;
                if(ind==-1){f=1;break;}
                nxt.b[ind]=1;
                nxt.u[j]=ind;
            }
            if(f)break;
            for(int j=0;j<k;j++)for(int ind:nxt.u)nxt.m[j]=max(nxt.m[j],a[ind][j]);
            nxt.s=accumulate(begin(nxt.m),end(nxt.m),0);
            pq.push(nxt);
        }
    }

    cout<<pq.top().s<<'\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...