//Author: Oliver-Matis Lill
//Around O(C N log(C)), A* search of solutions
#include<iostream>
#include<bitset>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
using namespace std;
vector<int> pairwise_min(vector<int> a, vector<int> b) {
vector<int> result(a.size());
for(int i=0; i<(int)a.size(); i++) {
result[i] = min(a[i], b[i]);
}
return result;
}
vector<int> pairwise_max(vector<int> a, vector<int> b) {
vector<int> result(a.size());
for(int i=0; i<(int)a.size(); i++) {
result[i] = max(a[i], b[i]);
}
return result;
}
int sum(vector<int> a) {
return accumulate(a.begin(), a.end(), 0);
}
struct Solution_State {
int expected;
vector<int> taken;
bitset<500> excluded;
bool operator<(Solution_State r) const {
return expected < r.expected;
}
};
int combs(int n, int k) {
int result = 1;
for(int i=n; i>n-k; i--) {
result *= i;
}
for(int i=1; i<=k; i++ ) {
result /= i;
}
return result;
}
int main() {
int n, k, c;
cin >> n >> k >> c;
c--;
vector<vector<int> > scores(n, vector<int>(k));
for(int i=0; i<n; i++) {
for(int j=0; j<k; j++) {
cin >> scores[i][j];
}
}
vector<vector<pair<int, int> > > order(k);
// vector<vector<vector<int> > > max_left(k, vector<vector<int> >(n, vector<int>(k, 0)));
for(int j=0; j<k; j++) {
for(int i=0; i<n; i++) {
order[j].push_back({scores[i][j], i});
}
sort(order[j].rbegin(), order[j].rend());
/*
bitset<500> excluded;
for(int i=0; i<n; i++) {
for(int o=0; i<n; o++) {
if(!excluded[o]) {
max_left[j][i] = pairwise_max(min_left[j][i], scores[o]);
}
}
excluded[i] = true;
}
*/
}
vector<int> solutions;
priority_queue<Solution_State> heap;
{
vector<int> max_per_event(k, 0);
for(int i=0; i<n; i++) {
max_per_event = pairwise_max(max_per_event, scores[i]);
}
heap.push(Solution_State({sum(max_per_event), {}, bitset<500>()}));
}
while((int)solutions.size() <= c+10 && heap.size() > 0) {
Solution_State sol = heap.top();
heap.pop();
if((int)sol.taken.size() == k) {
int left = k;
for(int j=0; j<k; j++) {
int index_taken = order[j][sol.taken[j]].second;
left -= !sol.excluded[index_taken];
sol.excluded[index_taken] = 1;
}
for(int i=0; i<combs(n-sol.excluded.count(), left) && (int)solutions.size() <= c+10; i++) {
solutions.push_back(sol.expected);
}
continue;
}
int j = sol.taken.size();
int overshot = 0;
vector<int> max_per_event(k, 0);
bitset<500> cur_excluded;
for(int i=0; i<n; i++) cur_excluded[i] = 1;
for(int i=n-1; i>=0; i--) {
if(!sol.excluded[order[j][i].second]) {
cur_excluded[order[j][i].second] = 0;
for(int o=0; o<j; o++) {
if(order[o][sol.taken[o]].second == order[j][i].second) {
overshot++;
}
}
max_per_event = pairwise_max(max_per_event, scores[order[j][i].second]);
if(overshot == j) {
vector<int> new_taken = sol.taken;
new_taken.push_back(i);
heap.push(Solution_State({sum(max_per_event), new_taken, cur_excluded}));
}
}
}
}
for(int i=max(0, c-9); i<c; i++) {
cerr << solutions[i] << ' ';
}
cerr << "| " << solutions[c] << " | ";
for(int i=c+1; i<c+10 && i < (int)solutions.size(); i++) {
cerr << solutions[i] << ' ';
}
cerr << '\n';
for(int i=0;i+1 < (int)solutions.size(); i++) {
if(solutions[i] < solutions[i+1]) {
cerr << "Invalid ordering\n";
throw 1;
}
}
{
vector<int> uniques = solutions;
uniques.erase(uniques.begin() + c + 1, uniques.end());
uniques.resize(unique(uniques.begin(), uniques.end()) - uniques.begin() );
cerr << uniques.size() << " unique values\n";
}
cout << solutions[c] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
2192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
16588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
2192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
