oj.uz

Submission #237965

# Submission time Handle Problem Language Result Execution time Memory
237965 2020-06-09T13:51:19 Z grt Olympiads (BOI19_olympiads) C++17
44 / 100
 599 ms 16980 KB 
#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-c];
		} 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() - c];
		} 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() - c];
		}
		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() - c];
		} 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() - c];
		} 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() - c];
		}
		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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct
3 Correct 10 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 16980 KB Output is correct
2 Correct 515 ms 16980 KB Output is correct
3 Correct 599 ms 16852 KB Output is correct
4 Correct 525 ms 16852 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct
3 Correct 10 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 542 ms 16980 KB Output is correct
6 Correct 515 ms 16980 KB Output is correct
7 Correct 599 ms 16852 KB Output is correct
8 Correct 525 ms 16852 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -