Submission #826607

#	Time	Username	Problem	Language	Result	Execution time	Memory
826607		QwertyPi	Olympiads (BOI19_olympiads)	C++14	13 / 100	2065 ms	16940 KiB

olympiads

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[511][6], p[511][6];
int r[511];

int n, k, c;

vector<int> C[6];
int t[6];

vector<pair<int, int>> V;

int __C(int n, int k){
	if(k > n || k < 0) return 0;
	int r = 1;
	for(int i = 1; i <= k; i++){
		r = r * (n - k + i) / i;
	}
	return r;
}

void rec(int i){
	if(i == -1){
		bool failed = false;
		for(int x = 0; x < k; x++){
			for(int y = 0; y < k; y++){
				if(p[t[y]][x] < p[t[x]][x]){
					failed = true; break;
				}
			}
			if(failed) break;
		}
		if(failed) return;
		vector<int> v;
		for(int j = 0; j < k; j++) {
			bool f = false;
			for(int i = 0; i < v.size(); i++) if(v[i] == t[j]) { f = true; break; }
			if(f) continue; v.push_back(t[j]);
		}
		int n0 = 0, k0 = v.size();
		for(int j = 0; j < n; j++){
			bool ok = true;
			for(int x = 0; x < k; x++){
				if(p[j][x] <= p[t[x]][x]){
					ok = false; break;
				}
			}
			if(ok) n0++;
		}
		int sc = 0; for(int x = 0; x < k; x++) sc += a[t[x]][x];
		if(__C(n0, k - k0) > 0) V.push_back({sc, __C(n0, k - k0)});
		return;
	}
	for(int j = 0; j < C[i].size(); j++){
		t[i] = C[i][j];
		rec(i - 1);
		t[i] = 0;
	}
}

int32_t main(){

	cin >> n >> k >> c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
		}
	}

	if(k == 1){
		vector<int> b;
		for(int i = 0; i < n; i++){
			b.push_back(a[i][0]);
		}
		sort(b.begin(), b.end(), [](int x, int y){ return x > y; });
		cout << b[c - 1] << endl;
		return 0;
	}else if(k == 2){
		vector<int> b;
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				b.push_back(max(a[i][0], a[j][0]) + max(a[i][1], a[j][1]));
			}
		}
		sort(b.begin(), b.end(), [](int x, int y){ return x > y; });
		cout << b[c - 1] << endl;
		return 0;
	}

	map<int, int> mp_needed;
	mp_needed[3] = 60; 24;
	mp_needed[4] = 30; 17;
	mp_needed[5] = 20; 14;
	mp_needed[6] = 20; 14;
	for(int i = 0; i < k; i++){
		vector<pair<int, int>> priority;
		for(int j = 0; j < n; j++) priority.push_back({a[j][i], j});
		sort(priority.begin(), priority.end(), [](auto p1, auto p2){ return p1.first > p2.first; });
		for(int j = 0; j < n; j++){
			p[priority[j].second][i] = j;
		}
		for(int j = 0; j < min(mp_needed[k], n); j++){
			C[i].push_back(priority[j].second);
		}
	}

	rec(k - 1);
	sort(V.begin(), V.end(), [](auto a, auto b){ return a.first > b.first; });

	for(auto [sc, cnt] : V){
		if(cnt >= c){
			cout << sc << endl;
			return 0;
		}
		c -= cnt;
	}
}

Compilation message (stderr)

olympiads.cpp: In function 'void rec(long long int)':
olympiads.cpp:39:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i = 0; i < v.size(); i++) if(v[i] == t[j]) { f = true; break; }
      |                   ~~^~~~~~~~~~
olympiads.cpp:40:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |    if(f) continue; v.push_back(t[j]);
      |    ^~
olympiads.cpp:40:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |    if(f) continue; v.push_back(t[j]);
      |                    ^
olympiads.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int j = 0; j < C[i].size(); j++){
      |                 ~~^~~~~~~~~~~~~
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:93:21: warning: statement has no effect [-Wunused-value]
   93 |  mp_needed[3] = 60; 24;
      |                     ^~
olympiads.cpp:94:21: warning: statement has no effect [-Wunused-value]
   94 |  mp_needed[4] = 30; 17;
      |                     ^~
olympiads.cpp:95:21: warning: statement has no effect [-Wunused-value]
   95 |  mp_needed[5] = 20; 14;
      |                     ^~
olympiads.cpp:96:21: warning: statement has no effect [-Wunused-value]
   96 |  mp_needed[6] = 20; 14;
      |                     ^~
olympiads.cpp:112:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |  for(auto [sc, cnt] : V){
      |           ^

• Subtask 1: 13 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32