#include<bits/stdc++.h>
//#include"tickets.h"
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf = 1e9;
using namespace std;
ll choose(ll n, ll k) {
if (n == 0)return 0;
if (k == 0)return 1;
if (k == n)return 1;
ll ans = 1;
rrep(i, n, (n-k) ) {
ll ny = i;
ans *= ny;
}
rep(i, 1, k + 1)ans /= i;
return ans;
}
vector<vector<ll>> choices(501, vector<ll>(7));
int main() {
cin.sync_with_stdio(false);
ll n, c, k;
rep(i, 0, 501) {
rep(j, 0, 6) {
if (i < j)continue;
ll val = choose(i, j);
if (val > 1e9)break;
choices[i][j] = val;
}
}
cin >> n >> k >> c;
vector<vector<ll>> v(n, vector<ll>(k));
rep(i, 0, n)rep(j, 0, k)cin >> v[i][j];
vector < vector<pair<ll, ll>>> vec(k);
rep(i, 0, n) {
rep(j, 0, k) {
vec[j].emplace_back(v[i][j], i);
}
}
trav(a, vec)sort(all(a),greater<>());
map<vector<int>, bool> mp;
vector<int> cur(k);
ll val = 0;
vector<vector<int>> sorted;
bitset<501> present;
ll mising = k;
rep(i, 0, k) {
if (!present[vec[i][cur[i]].second]) {
mising--;
present[vec[i][cur[i]].second] = 1;
}
}
val += choices[n - (k - mising)][mising];
mp[cur] = 1;
ll order = 0;
while (val<c) {
bool done = true;
vector<int> cur2=cur;
rep(i, 0, k) {
cur2[i]++;
done = mp[cur2];
cur2[i]--;
}
if (done) {
cur = sorted[order++];
}
vector<int> init(k, inf);
pair<ll, vector<int>> best=make_pair(inf,init);
rep(i, 0, k) {
cur2 = cur;
bool bad = false;
while (mp[cur2]) {
cur2[i]++;
if (cur2[i] == k) {
bad = true;
break;
}
//rep(j, 0, cur.size()) {
// if (i == j)continue;
// if(vec[j][cur2[j]].second == vec[i][cur2[i]].second)
//}
}
if (bad)continue;
rep(j, 0, k) {
if (j == i)continue;
if (vec[j][cur[j]].second == vec[i][cur[i]].second) {
cur2[j]++;
while (mp[cur2]) {
cur2[j]++;
if (cur2[j] == k) {
bad = true;
break;
}
}
}
if (bad) {
break;
}
}
if (bad)continue;
pair<ll, vector<int>> local = make_pair(0, cur2);
rep(j, 0, k) {
local.first += vec[j][cur[j]].first - vec[j][cur2[j]].first;
}
best = min(best, local);
}
cur2 = best.second;
sorted.push_back(cur2);
mp[cur2] = 1;
ll howmany = n;
bitset<501> visited;
bitset<501> present;
rep(i, 0, k) {
rrep(j, cur2[i], -1) {
if (!visited[vec[i][j].second]) {
howmany--;
visited[vec[i][j].second] = 1;
}
}
}
ll mising = k;
rep(i, 0, k) {
if (!present[vec[i][cur2[i]].second]) {
mising--;
present[vec[i][cur2[i]].second] = 1;
}
}
val += choices[howmany][mising];
if (val >= c)cur = cur2;
}
ll ans = 0;
rep(i, 0, k) {
ans += vec[i][cur[i]].first;
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
