oj.uz

Submission #130067

# Submission time Handle Problem Language Result Execution time Memory
130067 2019-07-13T20:34:06 Z TadijaSebez Olympiads (BOI19_olympiads) C++11
44 / 100
 192 ms 1240 KB 
#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);
}
int 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];
	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);
		}
	}
	printf(":D\n");
	return 0;
}

Compilation message

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:76: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:77: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 368 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 584 KB Output is correct
2 Correct 159 ms 1036 KB Output is correct
3 Correct 192 ms 1088 KB Output is correct
4 Correct 192 ms 1240 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 368 KB Output is correct
5 Correct 54 ms 584 KB Output is correct
6 Correct 159 ms 1036 KB Output is correct
7 Correct 192 ms 1088 KB Output is correct
8 Correct 192 ms 1240 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -