#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<vi> have;
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 main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,k,c;
cin >> n >> k >> c;
have.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].pb(peop[i][j]);
}
}
int mx=0;
array<int,6> inds;
for (int i=k-1; i>=0; i--) {
sort(all(have[i]));
have[i].erase(unique(all(have[i])),have[i].end());
mx+=have[i].back();
inds[i]=have[i].size()-1;
}
priority_queue<pair<int,array<int,6>>,vector<pair<int,array<int,6>>>,greater<pair<int,array<int,6>>>> q;
q.push({mx,inds});
set<array<int,6>> seen;
while (1) {
auto [s,inds]=q.top();
q.pop();
vi nums;
for (int i=0; i<k; i++) {
nums.pb(have[i][inds[i]]);
}
c-=clc(nums);
if (c<=0) {
cout << s << '\n';
break;
}
for (int i=0; i<k; i++) {
if (inds[i]==0) {
continue;
}
inds[i]--;
if (seen.count(inds)) {
inds[i]++;
continue;
}
s-=have[i][inds[i]+1]-have[i][inds[i]];
q.push({s,inds});
seen.insert(inds);
s+=have[i][inds[i]+1]-have[i][inds[i]];
inds[i]++;
}
}
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... |