oj.uz

Submission #238668

# Submission time Handle Problem Language Result Execution time Memory
238668 2020-06-12T09:54:58 Z grt Olympiads (BOI19_olympiads) C++17
0 / 100
 104 ms 21052 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 = 500+10;
int n,k,c;
int score[nax][6];
bool selected[nax];

struct Team {
	int cost;
	vi taken;
	vi status;
	bool operator < (const Team &T) const {
		return cost < T.cost;
	}
};

Team find_best_team(vi arr) {
	Team ans;
	ans.cost = 0;
	ans.taken = {};
	ans.status = arr;
	for(int i = 0; i < n; ++i) {
		selected[i] = 0;
		if(arr[i] == 1) {
			ans.taken.PB(i);
			selected[i] = 1;
		}
	}
	for(int j = (int)ans.taken.size(); j < k; ++j) {
		pi mx = {-1,-1};
		for(int i = 0; i < n; ++i) {
			if(arr[i] == 0 && !selected[i]) {
				mx = max(mx, {score[i][j], i});
			}
		}
		if(mx.ST == -1) {
			ans.cost = -1;
			return ans;
		}
		ans.taken.PB(mx.ND);
		selected[mx.ND] = 1;
	}
	for(int i = 0; i < 6; ++i) {
		int mx = -1;
		for(int x : ans.taken) mx = max(mx,score[x][i]);
		ans.cost += mx;
	}
	return ans;
}

priority_queue<Team>q;

int solve() {
	vi em(n);
	for(int i = 0; i < n; ++i) em[i] = 0;
	q.push(find_best_team(em));
	while(!q.empty()) {
		Team tm = q.top();
		q.pop();
		c--;
		if(c == 0) {
			return tm.cost;
		}
		vi arr = tm.status;
		for(int i = 0; i < k; ++i) {
			if(i > 0) {
				arr[tm.taken[i-1]] = 1;
			}
			arr[tm.taken[i]] = -1;
			Team tmp = find_best_team(arr);
			if(tmp.cost != -1) {
				q.push(tmp);
			}
		}
	}
	return -1;
}




int main() {_
	cin >> n >> k >> c;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < k; ++j) {
			cin >> score[i][j];
		}
	}
	cout << solve();
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 20996 KB Output is correct
2 Correct 67 ms 20944 KB Output is correct
3 Incorrect 100 ms 21052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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