#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]
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
