oj.uz

Submission #124908

# Submission time Handle Problem Language Result Execution time Memory
124908 2019-07-04T06:24:09 Z 구재현(#3056) Olympiads (BOI19_olympiads) C++14
44 / 100
 2000 ms 181312 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 - 1; i++) ans.push(-69);
	vis.insert(cnd);
	pq.push(cnd);
	ans.push(cost(cnd));
	for(int i = 0; i < c - 1; i++){
		auto x = pq.top();
		pq.pop();
		/*
		printf("[");
		for(auto &i : x) printf("%d", i);
		puts("]");
		printf("%lld\n", cost(x));*/
		for(int i=0; i<k; i++){
			for(int j=1; j<=n; j++){
				auto nxt = x;
				nxt[i] = j;
				sort(nxt.begin(), nxt.end());
				bool good = 1;
				for(int j=1; j<k; j++){
					if(nxt[j-1] == nxt[j]) good = 0;
				}
				if(!good) continue;
				int cst = cost(nxt);
				if(cst >= ans.top() && vis.find(nxt) == vis.end()){
					pq.push(nxt);
					vis.insert(nxt);
					ans.push(cst);
					ans.pop();
				}
			}
		}
	}
	auto x = pq.top();
	printf("%d\n", cost(x));
}

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 210 ms 1032 KB Output is correct
2 Correct 200 ms 1492 KB Output is correct
3 Correct 206 ms 1060 KB Output is correct
4 Correct 563 ms 18940 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 1272 KB Output is correct
2 Correct 97 ms 1244 KB Output is correct
3 Correct 83 ms 888 KB Output is correct
4 Correct 84 ms 888 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 1032 KB Output is correct
2 Correct 200 ms 1492 KB Output is correct
3 Correct 206 ms 1060 KB Output is correct
4 Correct 563 ms 18940 KB Output is correct
5 Correct 88 ms 1272 KB Output is correct
6 Correct 97 ms 1244 KB Output is correct
7 Correct 83 ms 888 KB Output is correct
8 Correct 84 ms 888 KB Output is correct
9 Execution timed out 2056 ms 181312 KB Time limit exceeded
10 Halted 0 ms 0 KB -