Submission #132852

#	Time	Username	Problem	Language	Result	Execution time	Memory
132852		rajarshi_basu	Olympiads (BOI19_olympiads)	C++14	0 / 100	2065 ms	49188 KiB

olympiads

#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( data d1, data d2){
	return d1.sum > d2.sum;
}

//queue<int*> q;
priority_queue<data,vector<data>, function<bool(data,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(valid.size() == 0){
		//cout << "EXITED" << endl;
		return 0;
	}
	set<int> goood;
	FOR(sortItem,k){
		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;
	
	int numT = k - taken.size();
	//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 = evaluateSpace(space,ans);
	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));
	}
}

void solve(){
	int arr[n];
	FOR(i,n)arr[i] = 2;
	processSubspace(arr);
	while(!pq.empty() or 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 (stderr)

olympiads.cpp: In function 'int evaluateSpace(int*, std::vector<int>&)':
olympiads.cpp:94:11: 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:96:7:
   FOR(j,good.size()){
       ~~~~~~~~~~~~~            
olympiads.cpp:96:3: note: in expansion of macro 'FOR'
   FOR(j,good.size()){
   ^~~
olympiads.cpp:101:16: 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:133:6:
  FOR(i,ans.size()){
      ~~~~~~~~~~~~              
olympiads.cpp:133:2: note: in expansion of macro 'FOR'
  FOR(i,ans.size()){
  ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32