oj.uz

Submission #972990

# Submission time Handle Problem Language Result Execution time Memory
972990 2024-05-01T11:34:55 Z Joshua_Andersson Olympiads (BOI19_olympiads) C++14
100 / 100
 207 ms 1600 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

typedef bitset<501> bset;
typedef tuple<int, vi, vi, bset> team;
struct compare {
	bool operator()(const team& a, const team& b)
	{
		return get<0>(a) < get<0>(b);
	}
	
};


signed main()
{
	fast();

	int n, k, c;
	cin >> n >> k >> c;

	vvi strength(n, vi(k));
	rep(i, n)
	{
		rep(j, k)
		{
			cin >> strength[i][j];
		}
	}

	priority_queue<team, vector<team>, compare> teams;
	vi start;
	rep(j, k)
	{
		int best = 0;
		int bestv = -1;
		rep(i, n)
		{
			if (strength[i][j] > bestv && find(all(start),i)==start.end())
			{
				best = i;
				bestv = strength[i][j];
			}
		}
		start.push_back(best);
	}
	
	auto getsum = [&](vi& team, vi& team2)
	{
		vi best(k, 0);
		repe(v, team)
		{
			rep(j, k)
			{
				best[j] = max(best[j], strength[v][j]);
			}
		}
		repe(v, team2)
		{
			rep(j, k)
			{
				best[j] = max(best[j], strength[v][j]);
			}
		}
		return accumulate(all(best), 0LL);
	};
	
	vi forced;
	teams.emplace(getsum(start, forced), start, forced, bset());

	rep(it, c-1)
	{
		int s;
		vi curr, forced;
		bset banned;
		tie(s, curr, forced, banned) = teams.top();
		teams.pop();
		
		while (curr.size())
		{
			vi newcurr(curr);
			bset newbanned(banned);
			newbanned[newcurr.back()] = 1;
			newcurr.pop_back();
			int bestv = -1;
			int best = -1;
			rep(j, n)
			{
				if (find(all(newcurr),j)==newcurr.end()&&!newbanned[j])
				{
					newcurr.push_back(j);
					if (getsum(newcurr, forced)>bestv)
					{
						best = j;
						bestv = getsum(newcurr, forced);
					}
					newcurr.pop_back();
				}
			}
			if (best == -1) break;
			newcurr.push_back(best);
			
			teams.emplace(getsum(newcurr, forced), newcurr, forced, newbanned);
			banned[curr.back()] = 1;
			forced.push_back(curr.back());
			curr.pop_back();
		}
	}

	cout << get<0>(teams.top());

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 604 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 23 ms 512 KB Output is correct
4 Correct 16 ms 480 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1336 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 11 ms 1144 KB Output is correct
4 Correct 9 ms 1084 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 600 KB Output is correct
2 Correct 42 ms 344 KB Output is correct
3 Correct 120 ms 888 KB Output is correct
4 Correct 195 ms 1592 KB Output is correct
5 Correct 69 ms 688 KB Output is correct
6 Correct 4 ms 828 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 604 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 23 ms 512 KB Output is correct
4 Correct 16 ms 480 KB Output is correct
5 Correct 8 ms 1336 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 11 ms 1144 KB Output is correct
8 Correct 9 ms 1084 KB Output is correct
9 Correct 69 ms 600 KB Output is correct
10 Correct 42 ms 344 KB Output is correct
11 Correct 120 ms 888 KB Output is correct
12 Correct 195 ms 1592 KB Output is correct
13 Correct 69 ms 688 KB Output is correct
14 Correct 4 ms 828 KB Output is correct
15 Correct 105 ms 592 KB Output is correct
16 Correct 50 ms 344 KB Output is correct
17 Correct 185 ms 1600 KB Output is correct
18 Correct 207 ms 1172 KB Output is correct
19 Correct 43 ms 348 KB Output is correct