oj.uz

Submission #544882

# Submission time Handle Problem Language Result Execution time Memory
544882 2022-04-03T03:32:05 Z skittles1412 Olympiads (BOI19_olympiads) C++17
100 / 100
 47 ms 8124 KB 
#include <ostream>
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 505;

struct Sol {
	int w, meq;
	array<int, 6> ans;
	vector<int> neq;

	bool operator<(const Sol& s) const {
		return w < s.w;
	}
};

int n, m, arr[maxn][6];

int opt(int ind, const vector<int>& ign) {
	bool bad[n] {};
	for (auto& a : ign) {
		bad[a] = true;
	}
	pair<int, int> ans {-1, -1};
	for (int i = 0; i < n; i++) {
		if (!bad[i]) {
			ans = max(ans, pair<int, int> {arr[i][ind], i});
		}
	}
	return ans.second;
}

vector<Sol> fracture(const Sol& s) {
	vector<Sol> ans;
	vector<int> ineq = s.neq;
	for (int i = s.meq; i < m; i++) {
		ineq.push_back(s.ans[i]);
		auto cneq = ineq;
		int w[6] {};
		array<int, 6> cur {};
		copy(s.ans.begin(), s.ans.begin() + i, cur.begin());
		for (int j = i; j < m; j++) {
			cur[j] = opt(j, cneq);
			if (cur[j] == -1) {
				goto loop;
			}
			cneq.push_back(cur[j]);
		}
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < m; k++) {
				w[k] = max(w[k], arr[cur[j]][k]);
			}
		}
		ineq.push_back(cur[i]);
		ans.push_back(Sol {
			accumulate(begin(w), end(w), 0),
			i,
			cur,
			ineq
		});
		ineq.pop_back();
	loop:;
	}
	return ans;
}

Sol iopt() {
	int w[6] {};
	array<int, 6> cur {};
	vector<int> neq;
	for (int i = 0; i < m; i++) {
		cur[i] = opt(i, neq);
		neq.push_back(cur[i]);
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			w[j] = max(w[j], arr[cur[i]][j]);
		}
	}
	return {accumulate(begin(w), end(w), 0), 0, cur, {}};
}

void solve() {
	int k;
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	dbg(sz(fracture({0, 0, {1, 0, 0, 0, 0, 0}, {1, 2}})));
	priority_queue<Sol> pq;
	pq.push(iopt());
	for (int i = 0; i < k - 1; i++) {
		auto x = pq.top();
		dbg(x.ans[0], x.ans[1], sz(x.neq), sz(fracture(x)));
		pq.pop();
		for (auto& a : fracture(x)) {
			pq.push(a);
			dbg(a.ans[0], a.ans[1]);
		}
		dbg("D");
	}
	dbg(sz(pq));
	cout << pq.top().w << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 448 KB Output is correct
3 Correct 6 ms 432 KB Output is correct
4 Correct 6 ms 468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 4 ms 724 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 456 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 21 ms 2252 KB Output is correct
4 Correct 28 ms 3056 KB Output is correct
5 Correct 25 ms 4564 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 448 KB Output is correct
3 Correct 6 ms 432 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 320 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 5 ms 456 KB Output is correct
10 Correct 6 ms 616 KB Output is correct
11 Correct 21 ms 2252 KB Output is correct
12 Correct 28 ms 3056 KB Output is correct
13 Correct 25 ms 4564 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 6 ms 456 KB Output is correct
16 Correct 16 ms 1976 KB Output is correct
17 Correct 47 ms 8124 KB Output is correct
18 Correct 11 ms 1236 KB Output is correct
19 Correct 6 ms 608 KB Output is correct