#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define il pair<int,ll>
#define li pair<ll,int>
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,ll>
#define vv vector
using namespace std;
const int MAXN = 501;
int n,k;
vv<int> all[MAXN];
multiset<int,greater<int> > allV;
// for subspace : 1 = taken, 0 = not to be taken. 2 = can be either.
struct data{
int* arr;
int sum;
data(int* a,int s){
arr = a;
sum = s;
}
};
bool comp(const data& d1,const data& d2){
return d1.sum < d2.sum;
}
//queue<int*> q;
priority_queue<data,vector<data>, function<bool(const data&,const data&)> > pq(comp);
int evaluateSpace(int* arr,vi& ans){
//cout << "ENTERED" << endl;
//FOR(i,n)cout << arr[i] << " ";cout << endl;
vi valid;
vi taken;
FOR(i,n){
if(arr[i] == 2)valid.pb(i);
else if(arr[i] == 1)taken.pb(i);
}
if(taken.size() == k){
int xx[k];
FOR(i,k)xx[i] = 0;
for(auto e : taken){
FOR(i,k)xx[i] = max(xx[i],all[e][i]);
}
int sum = 0;
FOR(i,k)sum += xx[i];
return sum;
}
if(valid.size() == 0)return 0;
int numT = k - taken.size();
if(valid.size() < numT){
return 0;
}
set<int> goood;
FOR(sortItem,k){
if(valid.size() == 0)break;
sort(valid.begin(), valid.end(),[&](int a,int b){
if(goood.find(a) != goood.end())return false;
if(goood.find(b) != goood.end())return true;
return all[a][sortItem] > all[b][sortItem];
});
goood.insert(valid[0]);
}
vi good;
for(auto e : goood)good.pb(e);
int mx = 0;
//cout << numT << endl;
//cout << good.size() << endl;
FOR(mask,1<<good.size()){
if(numT > good.size())break;
vi cc;
FOR(j,good.size()){
if(((1<<j)&mask) > 0){
cc.pb(good[j]);
}
}
if(cc.size() == numT){
// this is a candidate choice
int sum = 0;
int xx[k];
FOR(i,k)xx[i] = 0;
for(auto e : taken){
FOR(i,k)xx[i] = max(xx[i],all[e][i]);
}
for(auto e : cc){
FOR(i,k)xx[i] = max(xx[i],all[e][i]);
}
FOR(i,k)sum += xx[i];
if(sum > mx){
mx = sum;
ans = cc;
}
}
}
//cout << "EXITED" << endl;
return mx;
}
void processSubspace(int* space){
vi ans;
vi ans2;
int an;
try{
an = evaluateSpace(space,ans);
}catch(...){
while(1);
}
if(an == 0)return;
allV.insert(an);
//cout << an << endl;
// ans now contains the stuff that i am to take.
FOR(i,ans.size()){
int* arr = new int[n];
FOR(j,n)arr[j] = space[j];
FOR(j,i){
arr[ans[j]] = 1;
}
arr[ans[i]] = 0;
int x = evaluateSpace(arr,ans2);
pq.push(data(arr,x));
}
ans2.clear();
}
void solve(){
int arr[n];
FOR(i,n)arr[i] = 2;
processSubspace(arr);
while(!pq.empty() and allV.size() < 3000){
data d = pq.top();pq.pop();
processSubspace(d.arr);
}
}
int main(){
int c;
cin >> n >> k >> c;
FOR(i,n){
FOR(j,k){
int a;
cin >> a;
all[i].pb(a);
}
}
solve();
int ctr = 0;
for(auto e : allV){
ctr++;
if(c == ctr){
cout << e << endl;
return 0;
}
//cout << e << endl;
}
return 0;
}
Compilation message
olympiads.cpp: In function 'int evaluateSpace(int*, std::vector<int>&)':
olympiads.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(taken.size() == k){
~~~~~~~~~~~~~^~~~
olympiads.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(valid.size() < numT){
~~~~~~~~~~~~~^~~~~~
olympiads.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(numT > good.size())break;
~~~~~^~~~~~~~~~~~~
olympiads.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
olympiads.cpp:114:13:
FOR(j,good.size()){
~~~~~~~~~~~~~
olympiads.cpp:114:9: note: in expansion of macro 'FOR'
FOR(j,good.size()){
^~~
olympiads.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cc.size() == numT){
~~~~~~~~~~^~~~~~~
olympiads.cpp: In function 'void processSubspace(int*)':
olympiads.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
olympiads.cpp:157:9:
FOR(i,ans.size()){
~~~~~~~~~~~~
olympiads.cpp:157:5: note: in expansion of macro 'FOR'
FOR(i,ans.size()){
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
463 ms |
6664 KB |
Output is correct |
| 2 |
Correct |
473 ms |
6552 KB |
Output is correct |
| 3 |
Correct |
430 ms |
6544 KB |
Output is correct |
| 4 |
Correct |
127 ms |
6520 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
172 ms |
1480 KB |
Output is correct |
| 2 |
Correct |
137 ms |
1456 KB |
Output is correct |
| 3 |
Correct |
154 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
160 ms |
1276 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2053 ms |
5276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
463 ms |
6664 KB |
Output is correct |
| 2 |
Correct |
473 ms |
6552 KB |
Output is correct |
| 3 |
Correct |
430 ms |
6544 KB |
Output is correct |
| 4 |
Correct |
127 ms |
6520 KB |
Output is correct |
| 5 |
Correct |
172 ms |
1480 KB |
Output is correct |
| 6 |
Correct |
137 ms |
1456 KB |
Output is correct |
| 7 |
Correct |
154 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
160 ms |
1276 KB |
Output is correct |
| 9 |
Execution timed out |
2053 ms |
5276 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
