#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2020;
int n,k,c, a[maxn][maxn], ch[maxn][maxn];
vector<pair<int,int>> pts[maxn];
void solve() {
cin >> n >> k >> c;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < k; j++) {
cin >> a[i][j];
pts[j].pb(mp(a[i][j],i));
}
}
for(int i = 0; i <= n; i++) {
ch[i][0] = 1;
for(int j = 1; j <= i; j++) {
ch[i][j] = ch[i-1][j-1]+ch[i-1][j];
ch[i][j] = min(ch[i][j],c);
}
}
map<vector<int>,int> anst;
for(int j = 0; j < k; j++) {
sort(all(pts[j]),greater<pair<int,int>>());
}
priority_queue<pair<int,vector<int>>> pq;
map<vector<int>,int> pt;
vector<int> vbeg,vids;
int pbeg = 0;
for(int j = 0; j < k; j++) {
vbeg.pb(0);
pbeg+= pts[j][0].fr;
}
pq.push(mp(pbeg,vbeg));
pt[vbeg] = pbeg;
while(true) {
vector<int> v = pq.top().sc;
pq.pop();
bool okk = true;
for(int j = 0; j < k; j++) {
for(int i = 0; i < k; i++) {
int id = pts[i][v[i]].sc;
if(mp(a[id][j],id) > pts[j][v[j]]) {
okk = false;
}
}
}
// if(!okk) {
// for(int i = 0; i < k; i++) {
// cout << pts[i][v[i]].sc << " ";
// }cout << endl;
// for(int i = 0; i < k; i++) {
// cout << v[i] << " ";
// }cout << endl;
// cout << pt[v] << endl;
// continue;
// }
if(okk) {
set<int> fq;
for(int j = 0; j < k; j++) {
fq.insert(pts[j][v[j]].sc);
}
int qtd = 0;
for(int i = 1; i <= n; i++) {
int ok = 1;
for(int j = 0; j < k; j++) {
if(mp(a[i][j],i) >= pts[j][v[j]]) ok = 0;
}
qtd+= ok;
}
c-= ch[qtd][k-fq.size()]; //ways to do this = choose(qtd,k-fq.size())
// for(int i = 0; i < k; i++) {
// cout << pts[i][v[i]].sc << " ";
// }cout << endl;
// for(int i = 0; i < k; i++) {
// cout << v[i] << " ";
// }cout << endl;
// cout << pt[v] << endl;
// cout << ch[qtd][k-fq.size()] << " " << qtd << " " << k-fq.size() << endl << endl;
if(c <= 0) {
cout << pt[v] << endl;
return;
}
}
for(int j = 0; j < k; j++) {
if(v[j] != n-1) {
v[j]++;
if(pt.count(v)) {
v[j]--;
continue;
}
int p1 = 0;
for(int i = 0; i < k; i++) {
p1+= pts[i][v[i]].fr;
}
pt[v] = p1;
pq.push(mp(pt[v],v));
v[j]--;
// cout << " " << j << " " << p1 << endl;
}
}
}
// while(pq.size() && qtdc <= c) {
// vector<int> v = pq.top().sc;
// int p = pq.top().fr;
// pq.pop();
// qtdc++;
// vector<int> vt;
// for(auto x : v) {
// vt.pb(pts[j][x].sc);
// }
// sort(all(vt));
// anst[vt] = max(anst[vt],p);
// for(int i = 0; i < k; i++) {
// if(i < k-1 && v[i]+1 == v[i+1]) continue;
// if(i == k+1 && v[i] == n-1) continue;
// vector<int> v1 = v;
// v1[i]++;
// if(pt.count(v1)) continue;
// int p1 = 0;
// for(int i1 = 0; i1 < k; i1++) {
// p1+= pts[j][i1].fr;
// }
// pt[v1] = p1;
// pq.push(mp(p1,v1));
// }
// }
// vector<int> ans;
// for(auto X : anst) {
// ans.pb(X.sc);
// }
// sort(all(ans));
// cout << ans[c-1] << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5588 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
23 ms |
8464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2164 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
649 ms |
96536 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5372 KB |
Output is correct |
| 3 |
Correct |
20 ms |
7544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
7800 KB |
Output is correct |
| 5 |
Correct |
12 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
22 ms |
5740 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5588 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
23 ms |
8464 KB |
Output is correct |
| 5 |
Correct |
2 ms |
980 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1876 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2016 KB |
Output is correct |
| 8 |
Correct |
8 ms |
2164 KB |
Output is correct |
| 9 |
Correct |
649 ms |
96536 KB |
Output is correct |
| 10 |
Correct |
3 ms |
5372 KB |
Output is correct |
| 11 |
Correct |
20 ms |
7544 KB |
Output is correct |
| 12 |
Correct |
21 ms |
7800 KB |
Output is correct |
| 13 |
Correct |
12 ms |
7588 KB |
Output is correct |
| 14 |
Correct |
22 ms |
5740 KB |
Output is correct |
| 15 |
Correct |
18 ms |
6560 KB |
Output is correct |
| 16 |
Correct |
8 ms |
6100 KB |
Output is correct |
| 17 |
Correct |
24 ms |
8080 KB |
Output is correct |
| 18 |
Correct |
20 ms |
7488 KB |
Output is correct |
| 19 |
Correct |
3 ms |
5460 KB |
Output is correct |
