oj.uz

답안 #829135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829135 2023-08-18T05:19:32 Z 1075508020060209tc Olympiads (BOI19_olympiads) C++14
100 / 100
 10 ms 980 KB 
#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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 444 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 444 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 724 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 10 ms 496 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 8 ms 964 KB Output is correct
18 Correct 7 ms 596 KB Output is correct
19 Correct 1 ms 452 KB Output is correct