#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
signed main()
{
fast();
int n, k, c;
cin >> n >> k >> c;
vvi strength(n, vi(k));
rep(i, n)
{
rep(j, k)
{
cin >> strength[i][j];
}
}
typedef tuple<int, vi, vi> team;
priority_queue<team> teams;
vi start;
rep(j, k)
{
int best = 0;
int bestv = -1;
rep(i, n)
{
if (strength[i][j] > bestv && find(all(start),i)==start.end())
{
best = i;
bestv = strength[i][j];
}
}
start.push_back(best);
}
auto getsum = [&](vi& team)
{
vi best(k, 0);
repe(v, team)
{
rep(j, k)
{
best[j] = max(best[j], strength[v][j]);
}
}
return accumulate(all(best), 0LL);
};
auto getsum2 = [&](vi& team, vi& team2)
{
vi best(k, 0);
repe(v, team)
{
rep(j, k)
{
best[j] = max(best[j], strength[v][j]);
}
}
repe(v, team2)
{
rep(j, k)
{
best[j] = max(best[j], strength[v][j]);
}
}
return accumulate(all(best), 0LL);
};
teams.emplace(getsum(start), start, vi());
rep(it, c-1)
{
int s;
vi nonyes;
vi yes;
tie(s, nonyes, yes) = teams.top();
teams.pop();
rep(i, sz(nonyes))
{
vi newnon(nonyes);
newnon.erase(newnon.begin() + i);
vi newyes(yes);
newyes.push_back(nonyes[i]);
teams.emplace(getsum2(newnon, newyes), newnon, newyes);
}
rep(i, sz(nonyes))
{
vi newnon(nonyes);
newnon.erase(newnon.begin() + i);
int bestv = -1;
int best = -1;
rep(j, n)
{
if (find(all(newnon),j)==newnon.end()&&find(all(yes),j)==yes.end())
{
newnon.push_back(j);
if (getsum2(newnon,yes)>bestv)
{
best = j;
bestv = getsum2(newnon, yes);
}
newnon.pop_back();
}
}
newnon.push_back(best);
teams.emplace(getsum2(newnon, yes), newnon, yes);
}
}
cout << get<0>(teams.top());
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
3244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
430 ms |
3256 KB |
Output is correct |
| 3 |
Incorrect |
434 ms |
3700 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
