Submission #237964

#	Time	Username	Problem	Language	Result	Execution time	Memory
237964		grt	Olympiads (BOI19_olympiads)	C++17	0 / 100	540 ms	16892 KiB

olympiads

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 510;
int n,k,c;
int val[nax][6];
bool best[nax];
vi g = {};

int main() {_
	cin >> n >> k >> c;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < k; ++j) {
			cin >> val[i][j];
		}
	}
	if(k <= 3) {
		if(k == 1) {
			vi v = {};
			for(int i = 1; i <= n; ++i) v.PB(val[i][0]);
			sort(v.begin(),v.end());
			cout << v[n-k];
		} else if(k == 2) {
			vi v = {};
			for(int i = 1; i <= n; ++i) {
				for(int j = i+1; j <= n; ++j) {
					int w = max(val[i][0],val[j][0]) + max(val[i][1],val[j][1]);
					v.PB(w);
				}
			}
			sort(v.begin(), v.end());
			cout << v[(int)v.size() - k];
		} else if(k == 3) {
			vi v = {};
			for(int i = 1; i <= n; ++i) {
				for(int j = i+1; j <= n; ++j) {
					for(int ii=j+1; ii <= n; ++ii) {
						int w = max({val[i][0],val[j][0],val[ii][0]})  + max({val[i][1], val[j][1], val[ii][1]}) + max({val[i][2], val[j][2], val[ii][2]});
						v.PB(w);
					}
				}
			}
			sort(v.begin(), v.end());
			cout << v[(int)v.size() - k];
		}
		return 0;
	}
	if(n <= 40) {
		if(k == 4) {
			vi v = {};
			for(int i = 1; i <= n; ++i) {
				for(int j = i+1; j <= n; ++j) {
					for(int ii=j+1; ii <= n; ++ii) {
						for(int ii2=ii+1; ii2 <= n; ++ii2) {
							int w = 0;
							for(int x = 0; x < k; ++x) {
								w += max({val[i][x],val[j][x],val[ii][x],val[ii2][x]});
							}
							v.PB(w);
						}
					}
				}
			}
			sort(v.begin(), v.end());
			cout << v[(int)v.size() - k];
		} else if(k==5) {
			vi v = {};
			for(int i = 1; i <= n; ++i) {
				for(int j = i+1; j <= n; ++j) {
					for(int ii=j+1; ii <= n; ++ii) {
						for(int ii2=ii+1; ii2 <= n; ++ii2) {
							for(int ii3 = ii2+1; ii3 <= n; ++ii3) {
							int w = 0;
							for(int x = 0; x < k; ++x) {
								w += max({val[i][x],val[j][x],val[ii][x],val[ii2][x],val[ii3][x]});
							}
							v.PB(w);
							}
						}
					}
				}
			}
			sort(v.begin(), v.end());
			cout << v[(int)v.size() - k];
		} else {
			vi v = {};
			for(int i = 1; i <= n; ++i) {
				for(int j = i+1; j <= n; ++j) {
					for(int ii=j+1; ii <= n; ++ii) {
						for(int ii2=ii+1; ii2 <= n; ++ii2) {
							for(int ii3 = ii2+1; ii3 <= n; ++ii3) {
								for(int ii4=ii3+1; ii4<=n; ii4++) {
							int w = 0;
							for(int x = 0; x < k; ++x) {
								w += max({val[i][x],val[j][x],val[ii][x],val[ii2][x],val[ii3][x], val[ii4][x]});
							}
							v.PB(w);
							}
							}
						}
					}
				}
			}
			sort(v.begin(), v.end());
			cout << v[(int)v.size() - k];
		}
		return 0;
	}
	for(int j = 0; j < k; ++j) {
		pi mx = {0,0};
		for(int i = 1; i <= n; ++i) {
			if(best[i]) continue;
			mx = max(mx, {val[i][j], i});
		}
		best[mx.ND] = 1;
		g.PB(mx.ND);
	}
	cout << "-1";
}

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