Submission #130036

#	Time	Username	Problem	Language	Result	Execution time	Memory
130036		TadijaSebez	Olympiads (BOI19_olympiads)	C++11	31 / 100	2079 ms	143440 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int K=6;
int n,k,c;
int a[K][N];
bool in[N];
set<string> was;
int Val(vector<int> state)
{
	int ans=0;
	for(int i=0;i<k;i++)
	{
		int tmp=0;
		for(int j:state) tmp=max(tmp,a[i][j]);
		ans+=tmp;
	}
	return ans;
}
string ToString(vector<int> state)
{
	string ans;
	for(int i=0;i<k;i++) ans+=(char)state[i];
	return ans;
}
int main()
{
	scanf("%i %i %i",&n,&k,&c);
	for(int i=1;i<=n;i++) for(int j=0;j<k;j++) scanf("%i",&a[j][i]);
	vector<int> st;
	for(int j=0;j<k;j++)
	{
		int b=0;
		for(int i=1;i<=n;i++) if(b==0 || a[j][i]>a[j][b]) b=i;
		st.push_back(b);
		in[b]=1;
	}
	sort(st.begin(),st.end());
	st.erase(unique(st.begin(),st.end()),st.end());
	for(int i=1;i<=n;i++) if(!in[i] && st.size()<k) st.push_back(i);
	priority_queue<pair<int,vector<int>>> pq;
	auto Push=[&](vector<int> state)
	{
		sort(state.begin(),state.end());
		string s=ToString(state);
		if(!was.count(s))
		{
			pq.push({Val(state),state});
			was.insert(s);
		}
	};
	Push(st);
	int ans=0;
	while(c--)
	{
		ans=pq.top().first;
		vector<int> state=pq.top().second;
		pq.pop();
		for(int i=1;i<=n;i++)
		{
			bool ok=1;
			for(int j:state) if(j==i) ok=0;
			if(!ok) continue;
			vector<int> nxt=state;
			for(int j=0;j<k;j++)
			{
				nxt[j]=i;
				Push(nxt);
				nxt[j]=state[j];
			}
		}
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:40:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=n;i++) if(!in[i] && st.size()<k) st.push_back(i);
                                     ~~~~~~~~~^~
olympiads.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:29:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) for(int j=0;j<k;j++) scanf("%i",&a[j][i]);
                                             ~~~~~^~~~~~~~~~~~~~~

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