#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V> void __print(const pair<T, V> &x) {
cerr << '{';
__print(x.first);
cerr << ", ";
__print(x.second);
cerr << '}';
}
template <typename T> void __print(const T &x) {
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? ", " : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) \
cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \
_print(x); \
cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
#define int ll
int N, K, C;
vector<vector<int>> v;
struct fuck {
vector<int> in;
vector<bool> out;
vector<int> can;
int cnt = 0;
int tot = 0;
fuck(vector<int>& in1, vector<bool>& out1) {
in = in1;
out = out1;
solve();
}
void solve() {
for (auto x : in) can.pb(x);
for (int i = 0; i < K; i++) {
int Midx = 0, Mval = -1;
for (auto id : can) {
if (v[id][i] > Mval) {
Midx = id;
Mval = v[id][i];
}
}
rep(j, N) {
if (!out[j] && v[j][i] > Mval) {
Midx = j;
Mval = v[j][i];
}
}
tot += Mval;
can.pb(Midx);
}
sort(all(can));
can.erase(unique(all(can)), can.end());
int u = can.size();
int l = 0;
rep(i, N) l += (int)out[i];
cnt = 1;
for (int j = 1; j <= K - u; j++) {
cnt = cnt * (N + 1 - u - l - j) / j;
if (cnt > C) break;
}
if (cnt > C) cnt = C;
}
bool operator <(const fuck& ot) const {
return tot < ot.tot;
}
};
int32_t main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> K >> C;
rep(i, N) {
vector<int> tmp;
rep(i, K) {
int x; cin >> x; tmp.pb(x);
}
v.pb(tmp);
}
vector<bool> a(N);
vector<int> b;
int cntt = 0, tott = 0;
priority_queue<fuck> pq;
fuck st(b, a);
pq.push(st);
while (!pq.empty()) {
fuck t = pq.top();
pq.pop();
tott = t.tot;
cntt += t.cnt;
dbg(tott,t.cnt);
if (cntt >= C) {
//dbg("wtf?");
cout << tott; return 0;
}
//vector<int> can = t.can;
vector<int> in1 = t.in;
vector<int> can;
for (int i = in1.size(); i < t.can.size(); i++) can.pb(t.can[i]);
vector<bool> out = t.out;
int shit = N;
rep(i, N) shit -= out[i];
if (shit < K + 1) continue;
for (int i = 0; i < can.size(); i++) {
out[can[i]] = 1;
if (i >= 1) out[can[i - 1]] = 0;
if (i >= 1)in1.pb(can[i - 1]);
pq.push(fuck(in1, out));
}
}
}
Compilation message
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:143:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int i = in1.size(); i < t.can.size(); i++) can.pb(t.can[i]);
| ~~^~~~~~~~~~~~~~
olympiads.cpp:149:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int i = 0; i < can.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
1816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
65 ms |
1920 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
