oj.uz

Submission #124903

# Submission time Handle Problem Language Result Execution time Memory
124903 2019-07-04T06:15:25 Z 구재현(#3056) Olympiads (BOI19_olympiads) C++14
0 / 100
 2000 ms 216868 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
using lint = long long;
using pi = pair<lint, int>;

int n, k, c;
int a[MAXN][10];
priority_queue<int, vector<int>, greater<int> > ans;
set<vector<int>> vis;

int cost(vector<int> &x){
	int ax[10] = {};
	for(auto &i : x){
		for(int j=0; j<k; j++) ax[j] = max(ax[j], a[i][j]);
	}
	return accumulate(ax, ax + k, 0);
}

auto cmp = [](vector<int> &x, vector<int> &y){
	return cost(x) < cost(y);
};

priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);

int main(){
	cin >> n >> k >> c;
	for(int i=1; i<=n; i++){
		for(int j=0; j<k; j++){
			cin >> a[i][j];
		}
	}
	vector<int> cnd;
	for(int i=0; i<k; i++){
		pi ret(-1, -1);
		for(int j=1; j<=n; j++){
			ret = max(ret, pi(a[j][i], j));
		}
		cnd.push_back(ret.second);
	}
	sort(cnd.begin(), cnd.end());
	cnd.resize(unique(cnd.begin(), cnd.end()) - cnd.begin());
	for(int i=1; i<=n; i++){
		if(cnd.size() < k && find(cnd.begin(), cnd.end(), i) == cnd.end()) cnd.push_back(i);
	}
	sort(cnd.begin(), cnd.end());
	for(int i=0; i<c; i++) ans.push(-69);
	vis.insert(cnd);
	pq.push(cnd);
	ans.push(cost(cnd));
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
		/*
		printf("[");
		for(auto &i : x) printf("%d", i);
		puts("]");
		printf("%lld\n", cost(x));*/
		if(cost(x) < ans.top()){
			continue;
		}
		for(int i=0; i<k; i++){
			auto nxt = x;
			for(int j=1; j<=n; j++){
				nxt[i] = j;
				int cst = cost(nxt);
				if(cst <= ans.top()) continue;
				auto snxt = nxt;
				sort(snxt.begin(), snxt.end());
				bool good = 1;
				for(int j=1; j<k; j++){
					if(snxt[j-1] == snxt[j]) good = 0;
				}
				if(good && vis.find(snxt) == vis.end()){
					pq.push(snxt);
					ans.push(cost(snxt));
					vis.insert(snxt);
				}
			}
		}
	}
	while(ans.size() > c) ans.pop();
	printf("%d\n", ans.top());
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:44:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnd.size() < k && find(cnd.begin(), cnd.end(), i) == cnd.end()) cnd.push_back(i);
      ~~~~~~~~~~~^~~
olympiads.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size() > c) ans.pop();
        ~~~~~~~~~~~^~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 32.0

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