oj.uz

답안 #972658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972658 2024-04-30T20:09:19 Z Joshua_Andersson Olympiads (BOI19_olympiads) C++14
0 / 100
 434 ms 3700 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



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];
		}
	}

	typedef tuple<int, vi, vi> team;
	priority_queue<team> 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 best(k, 0);
		repe(v, team)
		{
			rep(j, k)
			{
				best[j] = max(best[j], strength[v][j]);
			}
		}
		return accumulate(all(best), 0LL);
	};
	auto getsum2 = [&](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);
	};
	teams.emplace(getsum(start), start, vi());

	rep(it, c-1)
	{
		int s;
		vi nonyes;
		vi yes;
		tie(s, nonyes, yes) = teams.top();
		teams.pop();

		rep(i, sz(nonyes))
		{
			vi newnon(nonyes);
			newnon.erase(newnon.begin() + i);
			vi newyes(yes);
			newyes.push_back(nonyes[i]);
			teams.emplace(getsum2(newnon, newyes), newnon, newyes);
		}
		rep(i, sz(nonyes))
		{
			vi newnon(nonyes);
			newnon.erase(newnon.begin() + i);
			int bestv = -1;
			int best = -1;
			rep(j, n)
			{
				if (find(all(newnon),j)==newnon.end()&&find(all(yes),j)==yes.end())
				{
					newnon.push_back(j);
					if (getsum2(newnon,yes)>bestv)
					{
						best = j;
						bestv = getsum2(newnon, yes);
					}
					newnon.pop_back();
				}
			}
			newnon.push_back(best);
			teams.emplace(getsum2(newnon, yes), newnon, yes);

		}
	}

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

	return 0;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 3244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 3456 KB Output is correct
2 Correct 430 ms 3256 KB Output is correct
3 Incorrect 434 ms 3700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -