oj.uz

답안 #124897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124897 2019-07-04T06:03:53 Z 윤교준(#3050) Olympiads (BOI19_olympiads) C++14
44 / 100
 2000 ms 54784 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

struct NOD {
	ll key;
	int cost;

	void f(vector<int> V) {
		key = 0;
		for(int t = 6-sz(V); t--;) V.eb(511);
		sorv(V);
		for(int i = 0; i < 6; i++)
			key |= ll(V[i]) << (9*i);
	}
	void g(vector<int> &V) {
		for(int i = 0; i < 6; i++) {
			int c = (key >> (9*i)) & 511;
			if(c < 501) V.eb(c);
			else break;
		}
	}

	bool operator < (const NOD &t) const {
		if(cost != t.cost) return cost > t.cost;
		return key < t.key;
	}
};

unordered_set<ll> CMP;
set<NOD> PQ;

int A[500][6];

int N, K, C;

void cal(NOD &nod) {
	nod.cost = 0;
	vector<int> V; nod.g(V);
	for(int i = 0; i < K; i++) {
		int mx = 0;
		for(int v : V)
			if(mx < A[v][i]) mx = A[v][i];
		nod.cost += mx;
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> K >> C;
	for(int i = 0; i < N; i++) for(int j = 0; j < K; j++) cin >> A[i][j];

	{
		bitset<500> chk;
		vector<int> V;
		for(int j = 0; j < K; j++) {
			int mx = -1, mxi = -1;
			for(int i = 0; i < N; i++) {
				if(A[i][j] <= mx) continue;
				mx = A[i][j];
				mxi = i;
			}
			if(!chk[mxi]) {
				V.eb(mxi);
				chk[mxi] = true;
			}
		}
		for(int t = K-sz(V); t--;) {
			for(int i = 0; i < N; i++)
				if(!chk[i]) {
					chk[i] = true;
					V.eb(i);
					break;
				}
		}
		NOD nod; nod.f(V);
		cal(nod);
		PQ.insert(nod);
		CMP.insert(nod.key);
	}

	bitset<500> chk;
	for(NOD nod; !PQ.empty();) {
		nod = *PQ.begin(); PQ.erase(PQ.begin()); C--;
		if(!C) {
			cout << nod.cost << endl;
			break;
		}
		chk.reset();
		vector<int> V; nod.g(V);
		for(int v : V) chk[v] = true;
		for(int i = 0; i < N; i++) if(!chk[i]) {
			NOD nxt;
			for(int j = 0; j < K; j++) {
				int bf = V[j];
				V[j] = i;
				nxt.f(V);
				cal(nxt);
				V[j] = bf;

				auto it = CMP.find(nxt.key);
				if(CMP.end() == it) {
					CMP.insert(nxt.key);
					PQ.insert(nxt);
				}
			}
		}
		for(int t = max(0, sz(PQ)-C-1); t--;) PQ.erase(prev(PQ.end()));
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 711 ms 6376 KB Output is correct
2 Correct 721 ms 6480 KB Output is correct
3 Correct 674 ms 6432 KB Output is correct
4 Correct 581 ms 2040 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 4100 KB Output is correct
2 Correct 197 ms 3860 KB Output is correct
3 Correct 236 ms 3948 KB Output is correct
4 Correct 198 ms 3716 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2037 ms 54784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 711 ms 6376 KB Output is correct
2 Correct 721 ms 6480 KB Output is correct
3 Correct 674 ms 6432 KB Output is correct
4 Correct 581 ms 2040 KB Output is correct
5 Correct 211 ms 4100 KB Output is correct
6 Correct 197 ms 3860 KB Output is correct
7 Correct 236 ms 3948 KB Output is correct
8 Correct 198 ms 3716 KB Output is correct
9 Execution timed out 2037 ms 54784 KB Time limit exceeded
10 Halted 0 ms 0 KB -