oj.uz

Submission #125009

# Submission time Handle Problem Language Result Execution time Memory
125009 2019-07-04T10:47:17 Z gs14004 Olympiads (BOI19_olympiads) C++17
100 / 100
 140 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 1276 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1276 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 79 ms 6440 KB Output is correct
2 Correct 77 ms 6192 KB Output is correct
3 Correct 42 ms 2228 KB Output is correct
4 Correct 47 ms 2740 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 11916 KB Output is correct
2 Correct 36 ms 1988 KB Output is correct
3 Correct 91 ms 8376 KB Output is correct
4 Correct 89 ms 8872 KB Output is correct
5 Correct 65 ms 5300 KB Output is correct
6 Correct 41 ms 1972 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1276 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1276 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 79 ms 6440 KB Output is correct
6 Correct 77 ms 6192 KB Output is correct
7 Correct 42 ms 2228 KB Output is correct
8 Correct 47 ms 2740 KB Output is correct
9 Correct 105 ms 11916 KB Output is correct
10 Correct 36 ms 1988 KB Output is correct
11 Correct 91 ms 8376 KB Output is correct
12 Correct 89 ms 8872 KB Output is correct
13 Correct 65 ms 5300 KB Output is correct
14 Correct 41 ms 1972 KB Output is correct
15 Correct 140 ms 11944 KB Output is correct
16 Correct 125 ms 11820 KB Output is correct
17 Correct 42 ms 2228 KB Output is correct
18 Correct 63 ms 4244 KB Output is correct
19 Correct 38 ms 2040 KB Output is correct