oj.uz

Submission #124914

# Submission time Handle Problem Language Result Execution time Memory
124914 2019-07-04T06:37:29 Z 구재현(#3056) Olympiads (BOI19_olympiads) C++14
100 / 100
 160 ms 11944 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;
vector<int> gph[MAXN];

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++){
		vector<pi> v;
		for(int j=1; j<=n; j++){
			v.emplace_back(a[j][i], j);
		}
		sort(v.rbegin(), v.rend());
		cnd.push_back(v[0].second);
		for(int j=1; j<=n; j++){
			gph[j].push_back(v[0].second);
		}
		for(int j=1; j<n; j++){
			gph[v[j-1].second].push_back(v[j].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());
	vis.insert(cnd);
	pq.push(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(auto &j : gph[x[i]]){
				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;
				if(vis.find(nxt) == vis.end()){
					pq.push(nxt);
					vis.insert(nxt);
				}
			}
		}
	}
	auto x = pq.top();
	printf("%d\n", cost(x));
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:52: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 11 ms 1272 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1272 KB Output is correct
4 Correct 7 ms 760 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6440 KB Output is correct
2 Correct 83 ms 6128 KB Output is correct
3 Correct 42 ms 2356 KB Output is correct
4 Correct 48 ms 2740 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 11932 KB Output is correct
2 Correct 38 ms 2040 KB Output is correct
3 Correct 97 ms 8488 KB Output is correct
4 Correct 95 ms 8744 KB Output is correct
5 Correct 68 ms 5304 KB Output is correct
6 Correct 45 ms 2100 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1272 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1272 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 82 ms 6440 KB Output is correct
6 Correct 83 ms 6128 KB Output is correct
7 Correct 42 ms 2356 KB Output is correct
8 Correct 48 ms 2740 KB Output is correct
9 Correct 110 ms 11932 KB Output is correct
10 Correct 38 ms 2040 KB Output is correct
11 Correct 97 ms 8488 KB Output is correct
12 Correct 95 ms 8744 KB Output is correct
13 Correct 68 ms 5304 KB Output is correct
14 Correct 45 ms 2100 KB Output is correct
15 Correct 160 ms 11944 KB Output is correct
16 Correct 134 ms 11928 KB Output is correct
17 Correct 40 ms 2228 KB Output is correct
18 Correct 67 ms 4100 KB Output is correct
19 Correct 41 ms 1972 KB Output is correct