Submission #921072

#	Time	Username	Problem	Language	Result	Execution time	Memory
921072		shoryu386	Olympiads (BOI19_olympiads)	C++17	13 / 100	2044 ms	108376 KiB

olympiads

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

#define int long long


int scores[507][6];
int n, k, c;

vector<pair<int, int>> res;
map<vector<int>, int> store[507][6];

void recur(int x, int remain, vector<int> cur, int cnt){
	//cout << x << ' ' << remain << ' ' << cnt << '\n';
	//for (auto y : cur) cout << y << ' ';
	//cout << "\n\n";
	
	if (x == n){
		if (remain == 0){
			int lol = 0;
			for (int y = 0; y < k; y++) lol += cur[y];
			res.push_back({lol, cnt});
		}
		return;
	}
	
	store[x+1][remain][cur] += cnt;
	
	if (remain != 0){
		for (int y = 0; y < k; y++){
			cur[y] = max(cur[y], scores[x][y]);
		}
		store[x+1][remain-1][cur] += cnt;
	}
}

main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> k >> c;
	
	for (int x = 0; x < n; x++){
		for (int y = 0; y < k; y++){
			cin >> scores[x][y];
		} 
	}
	
	vector<int> init;
	for (int x = 0; x < k; x++){
		init.push_back(LLONG_MIN/20);
	}
	
	store[0][k][init] = 1;
	
	for (int x = 0; x <= n; x++){
		for (int y = 0; y <= k; y++){
			while (!store[x][y].empty()){
				auto vals = *store[x][y].begin();
				
				recur(x, y, vals.first, vals.second);
				
				store[x][y].erase(store[x][y].begin());
			}
		}
	}
	
	sort(res.begin(), res.end(), greater<pair<int, int>>());
	//for (auto y : res){
	//	cout << y.first << ' ' << y.second << '\n';
	//}
	
	int sum = 0;
	for (int x = 0; x < res.size(); x++){
		sum += res[x].second;
		if (sum >= c){
			cout << res[x].first;
			break;
		}
	}
}

Compilation message (stderr)

olympiads.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:73:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int x = 0; x < res.size(); x++){
      |                  ~~^~~~~~~~~~~~

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