Submission #402781

#	Time	Username	Problem	Language	Result	Execution time	Memory
402781		Nicholas_Patrick	Olympiads (BOI19_olympiads)	C++17	44 / 100	492 ms	262148 KiB

olympiads

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

bool comp(const vector<int>& a, const vector<int>& b){
	int A=0, B=0;
	for(int i: a)A+=i;
	for(int i: b)B+=i;
	return A>B;
}
int main(){
	int n, k, c;
	scanf("%d%d%d", &n, &k, &c);
	vector<vector<int>> people(n, vector<int>(k));
	vector<vector<int>> possibilities(k, vector<int>(n));
	for(int i=0; i<n; i++)for(int j=0; j<k; j++)
		scanf("%d", &people[i][j]), possibilities[j][i]=people[i][j];
	for(auto& i: possibilities){
		sort(i.begin(), i.end());
		i.resize(unique(i.begin(), i.end())-i.begin());
	}
	vector<vector<int>> combos(1), combos2;
	combos.reserve(c*n);
	combos2.reserve(c*n);
	for(int i=0; i<k; i++){
		combos2.clear();
		for(auto& l: combos){
			for(int j: possibilities[i]){
				combos2.push_back(l);
				combos2.back().push_back(j);
			}
		}
		swap(combos, combos2);
		if(combos.size()>c){
			nth_element(combos.begin(), combos.begin()+c, combos.end(), comp);
			combos.resize(c);
		}
	}
	sort(combos.rbegin(), combos.rend(), comp);
	int last;
	while(c>0){
		if(combos.empty())
			return 0;
		auto x=move(combos.back());
		combos.pop_back();
		last=0;
		for(int i: x)
			last+=i;
		vector<vector<pair<int, int>>> candy(k+1, vector<pair<int, int>>());
		int mask=0;
		for(int i=n; i--;){
			int curr=0;
			for(int j=k; j--;){
				if(people[i][j]<=x[j]){
					if(people[i][j]==x[j])
						curr|=1<<j;
				}else{
					curr=-1;
					break;
				}
			}
			if(curr!=-1){
				mask|=curr;
				for(int j=k; j--;){
					if(people[i][j]==x[j])
						candy[j+1].emplace_back(curr, i);
				}
				candy[0].emplace_back(curr, i);
			}
		}
		if(mask+1!=1<<k or candy[0].size()<k)
			continue;
		vector<vector<int>> team{{0}}, team2;
		for(int i=0; i<k; i++){
			team2.clear();
			for(auto& j: team){
				if(j[0]>>i&1){
					for(auto l: candy[0]){
						if(find(j.begin()+1, j.end(), l.second)==j.end()){
							team2.push_back(j);
							team2.back().push_back(l.second);
							team2.back()[0]|=l.first;
						}
					}
				}else{
					for(auto l: candy[1+i]){
						if(find(j.begin()+1, j.end(), l.second)==j.end()){
							team2.push_back(j);
							team2.back().push_back(l.second);
							team2.back()[0]|=l.first;
						}
					}
				}
			}
			swap(team, team2);
			if(team.size()>=c*720)
				break;
		}
		for(auto& i: team)
			sort(i.begin()+1, i.end());
		sort(team.begin(), team.end());
		team.resize(unique(team.begin(), team.end())-team.begin());
		c-=team.size();
	}
	printf("%d\n", last);
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:36:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |   if(combos.size()>c){
      |      ~~~~~~~~~~~~~^~
olympiads.cpp:73:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |   if(mask+1!=1<<k or candy[0].size()<k)
      |                      ~~~~~~~~~~~~~~~^~
olympiads.cpp:98:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |    if(team.size()>=c*720)
      |       ~~~~~~~~~~~^~~~~~~
olympiads.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d%d", &n, &k, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d", &people[i][j]), possibilities[j][i]=people[i][j];
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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