#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
// この場面ではもう vector<vector<int>> を使うしかないのでは
const int MAX_N = 20;
int N, K, C, A[509][6], S[509][3];
vector<int> Z1, Z2;
vector<int> V[3 * MAX_N + 9]; // 84 MiB
vector<long long> U[6 * MAX_N + 9], D[6 * MAX_N + 9];
void solve(int Z, int ty) {
for (int i = 0; i <= 3 * MAX_N; i++) V[i].clear();
if (Z == 0) {
V[0].push_back(0);
}
if (Z == 1) {
for (int i = 0; i < N; i++) {
int R[3] = { 0, 0, 0 };
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[i][l]);
V[R[0] + R[1]].push_back(i);
}
}
if (Z == 2) {
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
int R[3] = { 0, 0, 0 };
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[i][l]);
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[j][l]);
V[R[0] + R[1]].push_back(i + (j << 10));
}
}
}
if (Z == 3) {
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
for (int k = j + 1; k < N; k++) {
int R[3] = { 0, 0, 0 };
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[i][l]);
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[j][l]);
for (int l = 0; l < Z; l++) R[l] = max(R[l], S[k][l]);
V[R[0] + R[1] + R[2]].push_back(i + (j << 10) + (k << 20));
}
}
}
}
for (int i = 3 * MAX_N; i >= 0; i--) {
for (int j = 0; j < V[i].size(); j++) {
if (ty == 1) {
Z1.push_back(V[i][j]);
if (Z1.size() == 2500) break;
}
if (ty == 2) {
Z2.push_back(V[i][j]);
if (Z2.size() == 2500) break;
}
}
if (ty == 1 && Z1.size() == 2500) break;
if (ty == 2 && Z2.size() == 2500) break;
}
}
vector<long long> final_calc(int adds, vector<int> ban) {
vector<long long> I;
if (adds == 0) {
long long r = 0;
for (int i = 0; i < K; i++) r += (ban[i] << (10 * i));
I.push_back(r);
}
if (adds == 1) {
for (int i = 0; i < K; i++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
if (flag1 == true) continue;
int u[6] = { i, -1, -1, -1, -1, -1 };
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
sort(u, u + K);
long long s = 0;
for (int r = 0; r < K; r++) s += (u[r] << (10 * r));
I.push_back(s);
if (I.size() == 2000) break;
}
}
if (adds == 2) {
for (int i = 0; i < K; i++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
if (flag1 == true) continue;
for (int j = i + 1; j < K; j++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
if (flag1 == true) continue;
int u[6] = { i, j, -1, -1, -1, -1 };
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
sort(u, u + K);
long long s = 0;
for (int r = 0; r < K; r++) s += (u[r] << (10 * r));
I.push_back(s);
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
}
if (adds == 3) {
for (int i = 0; i < K; i++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
if (flag1 == true) continue;
for (int j = i + 1; j < K; j++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
if (flag1 == true) continue;
for (int k = j + 1; k < K; k++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
if (flag1 == true) continue;
int u[6] = { i, j, k, -1, -1, -1 };
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
sort(u, u + K);
long long s = 0;
for (int r = 0; r < K; r++) s += (u[r] << (10 * r));
I.push_back(s);
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
}
if (adds == 4) {
for (int i = 0; i < K; i++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
if (flag1 == true) continue;
for (int j = i + 1; j < K; j++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
if (flag1 == true) continue;
for (int k = j + 1; k < K; k++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
if (flag1 == true) continue;
for (int l = k + 1; l < K; l++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == l) flag1 = true; }
if (flag1 == true) continue;
int u[6] = { i, j, k, l, -1, -1 };
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
sort(u, u + K);
long long s = 0;
for (int r = 0; r < K; r++) s += (u[r] << (10 * r));
I.push_back(s);
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
}
if (adds == 5) {
for (int i = 0; i < K; i++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
if (flag1 == true) continue;
for (int j = i + 1; j < K; j++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
if (flag1 == true) continue;
for (int k = j + 1; k < K; k++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
if (flag1 == true) continue;
for (int l = k + 1; l < K; l++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == l) flag1 = true; }
if (flag1 == true) continue;
for (int m = l + 1; m < K; m++) {
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == m) flag1 = true; }
if (flag1 == true) continue;
int u[6] = { i, j, k, l, m,-1 };
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
sort(u, u + K);
long long s = 0;
for (int r = 0; r < K; r++) s += (u[r] << (10 * r));
I.push_back(s);
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
if (I.size() == 2000) break;
}
}
return I;
}
int main() {
cin >> N >> K >> C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) cin >> A[i][j];
}
int mid = (K / 2);
for (int i = 0; i < N; i++) {
for (int j = 0; j < mid; j++) S[i][j] = A[i][j];
}
solve(mid, 1);
for (int i = 0; i < N; i++) {
for (int j = mid; j < K; j++) S[i][j - mid] = A[i][j];
}
solve(K - mid, 2);
for (int i = 0; i < Z1.size(); i++) {
for (int j = 0; j < Z2.size(); j++) {
vector<int> E;
int t1 = Z1[i], t2 = Z2[j];
for (int k = 0; k < mid; k++) { E.push_back(t1 & 1023); t1 >>= 10; }
for (int k = 0; k < N - mid; k++) { E.push_back(t2 & 1023); t2 >>= 10; }
sort(E.begin(), E.end());
E.erase(unique(E.begin(), E.end()), E.end());
int R[6] = { 0, 0, 0, 0, 0, 0 };
for (int k = 0; k < E.size(); k++) {
for (int l = 0; l < K; l++) R[l] = max(R[l], A[E[k]][l]);
}
int sum = 0; for (int l = 0; l < K; l++) sum += R[l];
long long r = ((long long)E.size() << 60);
for (int k = 0; k < E.size(); k++) r += ((1LL * E[k]) << (10 * k));
U[sum].push_back(r);
}
}
int cnts = 0;
for (int i = 6 * MAX_N; i >= 0; i--) {
sort(U[i].begin(), U[i].end());
U[i].erase(unique(U[i].begin(), U[i].end()), U[i].end());
for (int j = 0; j < U[i].size(); j++) {
int sz = (U[i][j] >> 60); long long t3 = U[i][j];
vector<int> B; for (int k = 0; k < sz; k++) { B.push_back(t3 & 1023); t3 >>= 10; }
vector<long long> V = final_calc(K - sz, B);
for (int k = 0; k < V.size(); k++) D[i].push_back(V[k]);
cnts++;
if (cnts == 2500) break;
}
if (cnts == 2500) break;
}
int ptr = 0;
for (int i = 6 * MAX_N; i >= 0; i--) {
sort(D[i].begin(), D[i].end());
D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
ptr += (int)D[i].size();
if (ptr >= K) {
cout << i << endl;
break;
}
}
return 0;
}
Compilation message
olympiads.cpp: In function 'void solve(int, int)':
olympiads.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < V[i].size(); j++) {
~~^~~~~~~~~~~~~
olympiads.cpp: In function 'std::vector<long long int> final_calc(int, std::vector<int>)':
olympiads.cpp:78:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
~~^~~~~~~~~~~~
olympiads.cpp:94:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:98:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:102:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
~~^~~~~~~~~~~~
olympiads.cpp:116:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:120:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:124:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:128:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
~~^~~~~~~~~~~~
olympiads.cpp:144:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:148:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:152:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:156:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == l) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:160:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
~~^~~~~~~~~~~~
olympiads.cpp:178:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == i) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:182:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == j) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:186:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == k) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:190:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == l) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:194:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
bool flag1 = false; for (int r = 0; r < ban.size(); r++) { if (ban[r] == m) flag1 = true; }
~~^~~~~~~~~~~~
olympiads.cpp:198:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < ban.size(); r++) u[adds + r] = ban[r];
~~^~~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:237:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Z1.size(); i++) {
~~^~~~~~~~~~~
olympiads.cpp:238:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < Z2.size(); j++) {
~~^~~~~~~~~~~
olympiads.cpp:248:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < E.size(); k++) {
~~^~~~~~~~~~
olympiads.cpp:253:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < E.size(); k++) r += ((1LL * E[k]) << (10 * k));
~~^~~~~~~~~~
olympiads.cpp:264:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < U[i].size(); j++) {
~~^~~~~~~~~~~~~
olympiads.cpp:269:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < V.size(); k++) D[i].push_back(V[k]);
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
101044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
