Submission #829135

#	Time	Username	Problem	Language	Result	Execution time	Memory
829135		1075508020060209tc	Olympiads (BOI19_olympiads)	C++14	100 / 100	10 ms	980 KiB

olympiads

#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;int K;
int ar[1010][8];
int br[8][1010];
int rbr[1010][8];
int cmpcst;
bool cmp(int i,int j){
if(ar[i][cmpcst]>ar[j][cmpcst]){return 1;}
if(ar[i][cmpcst]<ar[j][cmpcst]){return 0;}
return i<j;
}

bool valid(vector<int>vc){
for(int i=1;i<=m;i++){
        int idi=br[i][vc[i]];
    for(int j=1;j<=m;j++){
        int idj=br[j][vc[j]];
        if(idi==idj){continue;}
        if(ar[idj][i]>ar[idi][i]){return 0;}
        if(ar[idj][i]==ar[idi][i]&&idj<idi){return 0;}
    }
}
return 1;
}
int comb(int x,int y){
if(x==y){return 1;}
if(y>x){return 0;}
if(y==0){return 1;}
int ret=1;
for(int i=1;i<=y;i++){
    ret*=x-i+1;
    ret/=i;
}
return ret;
}
int vcvl(vector<int>vc){
int ret=0;
for(int i=1;i<=m;i++){
    ret+=ar[br[i][vc[i]]][i];
}
return ret;
}

int cal(vector<int>vc){
set<int>st;
for(int i=1;i<=m;i++){st.insert(br[i][vc[i]]);}
if(!valid(vc)){return 0;}
int nd=m-(long long)st.size();
int lft=0;
for(int j=vc[1]+1;j<=n;j++){
    int id=br[1][j];
    int ok=1;
    for(int i=2;i<=m;i++){
        if(rbr[id][i]<=vc[i]){ok=0;break;}
    }
    lft+=ok;
}
return comb(lft,nd);
}

signed main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ar[i][j];
            br[j][i]=i;
        }
    }
    for(int i=1;i<=m;i++){
        cmpcst=i;
        sort(br[i]+1,br[i]+n+1,cmp);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            rbr[br[i][j]][i]=j;
        }
    }
    /*
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cout<<br[i][j]<<" ";
        }cout<<endl;
    }
    cout<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cout<<ar[br[i][j]][i]<<" ";
        }cout<<endl;
    }*/
    priority_queue<pair<int,pair<int,vector<int>>>>pq;
    vector<int>vc;
    for(int i=0;i<=m;i++){
        vc.push_back(1);
    }
    K-=cal(vc);
    if(K<=0){cout<<vcvl(vc)<<endl;return 0;}
   // cout<<cal(vc)<<" "<<vcvl(vc)<<endl;
    for(int i=1;i<=m;i++){
        vector<int>nvc=vc;
        nvc[i]++;
        pq.push({vcvl(nvc),{i,nvc}});
    }
    int ans=0;
    while(pq.size()){
        ans=pq.top().first;
        int nw=pq.top().second.first;
        vc=pq.top().second.second;
        pq.pop();
        int cnt=cal(vc);
        K-=cnt;
       /* cout<<ans<<" "<<nw<<" "<<cnt<<" ";
        for(int i=1;i<=m;i++){
            cout<<vc[i];
        }cout<<endl;
        */
        if(K<=0){cout<<ans<<endl;return 0;}
        vector<int>tvc=vc;
        if(vc[nw]+1<=n){
            tvc[nw]+=1;
            pq.push({vcvl(tvc),{nw,tvc}});
        }
       // tvc=vc;
        for(int j=nw+1;j<=m;j++){
            tvc=vc;
            tvc[j]++;
            pq.push({vcvl(tvc),{j,tvc}});
        }
    }

}

Compilation message (stderr)

olympiads.cpp:1:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
      |                                                               ^
olympiads.cpp:1:63: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
olympiads.cpp:10:21: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   10 | bool cmp(int i,int j){
      |                     ^
olympiads.cpp:10:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
olympiads.cpp:16:25: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   16 | bool valid(vector<int>vc){
      |                         ^
olympiads.cpp:16:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
olympiads.cpp:28:21: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   28 | int comb(int x,int y){
      |                     ^
olympiads.cpp:28:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
olympiads.cpp:39:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   39 | int vcvl(vector<int>vc){
      |                       ^
olympiads.cpp:39:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
olympiads.cpp:47:22: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   47 | int cal(vector<int>vc){
      |                      ^
olympiads.cpp:47:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
olympiads.cpp:64:13: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   64 | signed main()
      |             ^
olympiads.cpp:64:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

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