#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
vector<set<int>> have;
vi add;
vector<vi> peop;
int clc(vi& goal) {
vector<vi> dp(goal.size()+1,vi(1<<goal.size(),0));
dp[0][0]=1;
for (int i=0; i<peop.size(); i++) {
for (int l=goal.size()-1; l>=0; l--) {
for (int j=dp[0].size()-1; j>=0; j--) {
int newj=j;
for (int k=0; k<goal.size(); k++) {
if (goal[k]<peop[i][k]) {
newj=-1;
break;
}
if (goal[k]==peop[i][k]) {
newj|=(1<<k);
}
}
if (newj==-1) {
break;
}
dp[l+1][newj]+=dp[l][j];
if (dp[l+1][newj]>10000) {
dp[l+1][newj]=10000;
}
}
}
}
return dp.back().back();
}
int cnt(int a, int ind, vi& goal) {
if (a<0 || (ind<have.size() && a>add[ind])) {
return 0;
}
if (ind==have.size()) {
if (a==0) {
return clc(goal);
}
return 0;
}
int ret=0;
for (auto it=have[ind].rbegin(); it!=have[ind].rend(); it++) {
goal.pb(*it);
ret+=cnt(a-*it,ind+1,goal);
goal.pop_back();
if (ret>10000) {
ret=10000;
break;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,k,c;
cin >> n >> k >> c;
have.resize(k);
add.resize(k);
peop.resize(n,vi(k,0));
for (int i=0; i<n; i++) {
for (int j=0; j<k; j++) {
cin >> peop[i][j];
have[j].insert(peop[i][j]);
}
}
int mx=0;
for (int i=k-1; i>=0; i--) {
mx+=*prev(have[i].end());
add[i]=mx;
}
vi goal;
for (int sco=mx; sco>=0; sco--) {
c-=cnt(sco,0,goal);
if (c<=0) {
cout << sco << '\n';
break;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |