oj.uz

Submission #921088

# Submission time Handle Problem Language Result Execution time Memory
921088 2024-02-03T09:56:34 Z shoryu386 Olympiads (BOI19_olympiads) C++17
0 / 100
 2000 ms 40428 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long


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

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

int stop;

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 == stop){
		res1[remain].push_back({cur, 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;
	}
}

void recur2(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){
		res2[remain].push_back({cur, 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;
	stop = n/2;
	
	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 <= stop; 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());
			}
		}
	}
	
	store[stop][k][init] = 1;
	for (int x = stop; x <= n; x++){
		for (int y = 0; y <= k; y++){
			while (!store[x][y].empty()){
				auto vals = *store[x][y].begin();
				
				recur2(x, y, vals.first, vals.second);
				
				store[x][y].erase(store[x][y].begin());
			}
		}
	}
	
	int ans[100]; memset(ans, 0, sizeof(ans));
	
	for (int x = 0; x <= k; x++){
		for (auto r1 : res1[x]){
			for (auto r2 : res2[k-x]){
				
				int kek = 0;
				for (int z = 0; z < k; z++){
					kek += max(r1.first[z], r2.first[z]);
				}
				
				ans[kek] += r1.second * r2.second;
			}
		}
	}
	
	int sum = 0;
	for (int x = 99; x > -1; x--){
		sum += ans[x];
		if (sum >= c){
			cout << x;
			break;
		}
	}
}

Compilation message

olympiads.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 438 ms 8072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 13916 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 40428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 438 ms 8072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -