Submission #130077

#	Time	Username	Problem	Language	Result	Execution time	Memory
130077		TadijaSebez	Olympiads (BOI19_olympiads)	C++11	100 / 100	316 ms	1992 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
const int N=505;
const int K=6;
int a[K][N],n,k,c;
vector<int> vals[K];
int Val(vector<int> state)
{
	int ans=0;
	for(int i=0;i<k;i++) ans+=vals[i][state[i]];
	return ans;
}
void Answer(vector<int> state)
{
	printf("%i\n",Val(state));
	exit(0);
}
ll cnt[1<<K],dp[K+1][1<<K],use[K+1];
ll Get(vector<int> state)
{
	for(int i=0;i<1<<k;i++) cnt[i]=0;
	for(int i=1;i<=n;i++)
	{
		bool ok=1;
		int mask=0;
		for(int j=0;j<k;j++)
		{
			if(a[j][i]>vals[j][state[j]]) ok=0;
			if(a[j][i]==vals[j][state[j]]) mask|=1<<j;
		}
		if(ok) cnt[mask]++;
	}
	for(int i=0;i<=k;i++) for(int j=0;j<1<<k;j++) dp[i][j]=0;
	dp[0][0]=1;
	for(int l=0;l<1<<k;l++)
	{
		for(int i=0;i<=k;i++)
		{
			use[i]=1;
			for(int j=0;j<i;j++) use[i]*=cnt[l]-j;
			for(int j=1;j<=i;j++) use[i]/=j;
		}
		for(int i=k;i>=0;i--) for(int j=0;j<1<<k;j++)
		{
			for(int r=1;r<=k-i;r++)
			{
				dp[i+r][j|l]+=dp[i][j]*use[r];
			}
		}
	}
	return dp[k][(1<<k)-1];
}
void Check(vector<int> state)
{
	ll del=Get(state);
	if(del>=c) Answer(state);
	c-=del;
}
vector<int> Next(vector<int> state, int t)
{
	state[t]++;
	if(state[t]<vals[t].size()) return state;
	else return vector<int>(0);
}
set<string> was;
string ToString(vector<int> state)
{
	string ans;
	for(int i=0;i<k;i++)
	{
		ans+=(char)(state[i]/250);
		ans+=(char)(state[i]%250);
	}
	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]),vals[j].push_back(a[j][i]);
	for(int i=0;i<k;i++)
	{
		sort(vals[i].rbegin(),vals[i].rend());
		vals[i].resize(unique(vals[i].begin(),vals[i].end())-vals[i].begin());
	}
	priority_queue<pair<int,vector<int>>> pq;
	vector<int> st;
	for(int j=0;j<k;j++) st.push_back(0);
	auto Push=[&](vector<int> state)
	{
		string s=ToString(state);
		if(!was.count(s))
		{
			pq.push({Val(state),state});
			was.insert(s);
		}
	};
	Push(st);
	while(pq.size())
	{
		vector<int> state=pq.top().second;
		pq.pop();
		Check(state);
		for(int i=0;i<k;i++)
		{
			vector<int> nxt=Next(state,i);
			if(nxt.size()) Push(nxt);
		}
	}
	return -1;
}

Compilation message (stderr)

olympiads.cpp: In function 'std::vector<int> Next(std::vector<int>, int)':
olympiads.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(state[t]<vals[t].size()) return state;
olympiads.cpp: In function 'int main()':
olympiads.cpp:80: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:81:65: 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]),vals[j].push_back(a[j][i]);
                                             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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