oj.uz

Submission #130036

# Submission time Handle Problem Language Result Execution time Memory
130036 2019-07-13T19:21:27 Z TadijaSebez Olympiads (BOI19_olympiads) C++11
31 / 100
 2000 ms 143440 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 9704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 13152 KB Output is correct
2 Correct 235 ms 11712 KB Output is correct
3 Correct 260 ms 12480 KB Output is correct
4 Correct 252 ms 11848 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 143440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 9704 KB Output isn't correct
2 Halted 0 ms 0 KB -