oj.uz

Submission #124898

# Submission time Handle Problem Language Result Execution time Memory
124898 2019-07-04T06:04:13 Z 구재현(#3056) Olympiads (BOI19_olympiads) C++14
44 / 100
 2000 ms 208548 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);
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
	//	printf("[");
	//	for(auto &i : x) printf("%d", i);
	//	puts("]");
		if(cost(x) > ans.top()){
			ans.push(cost(x));
			ans.pop();
		}
		else 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);
					vis.insert(snxt);
				}
			}
		}
	}
	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);
      ~~~~~~~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 19124 KB Output is correct
2 Correct 732 ms 18968 KB Output is correct
3 Correct 737 ms 18916 KB Output is correct
4 Correct 650 ms 18908 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 14068 KB Output is correct
2 Correct 460 ms 11760 KB Output is correct
3 Correct 552 ms 13088 KB Output is correct
4 Correct 458 ms 12068 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 19124 KB Output is correct
2 Correct 732 ms 18968 KB Output is correct
3 Correct 737 ms 18916 KB Output is correct
4 Correct 650 ms 18908 KB Output is correct
5 Correct 585 ms 14068 KB Output is correct
6 Correct 460 ms 11760 KB Output is correct
7 Correct 552 ms 13088 KB Output is correct
8 Correct 458 ms 12068 KB Output is correct
9 Execution timed out 2064 ms 208548 KB Time limit exceeded
10 Halted 0 ms 0 KB -