oj.uz

Submission #124909

# Submission time Handle Problem Language Result Execution time Memory
124909 2019-07-04T06:33:40 Z 윤교준(#3050) Olympiads (BOI19_olympiads) C++14
100 / 100
 962 ms 10832 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 upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

struct NOD {
	vector<int> V;
	ll key;
	int cost;

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

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

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

int A[500][6];
int O[6][500], RO[6][500];

int N, K, C;

void cal(NOD &nod) {
	nod.cost = 0;
	for(int i = 0; i < K; i++) {
		int mx = 0;
		for(int v : nod.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];

	for(int j = 0; j < K; j++) {
		iota(O[j], O[j]+N, 0);
		sort(O[j], O[j]+N, [&](int a, int b) {
			if(A[a][j] != A[b][j]) return A[a][j] > A[b][j];
			return a < b;
		});
		for(int i = 0; i < N; i++)
			RO[j][O[j][i]] = i;
	}

	{
		bitset<500> chk;
		vector<int> V;
		for(int j = 0; j < K; j++) {
			for(int oi = 0, i;; oi++) {
				i = O[j][oi];
				if(chk[i]) continue;
				V.eb(i);
				chk[i] = true;
				break;
			}
		}
		NOD nod; nod.f(V);
		cal(nod);
		CMP.insert(nod.key);
		PQ.push(nod);
		//PQ.insert(nod);
	}

	bitset<500> chk;
	for(NOD nod; !PQ.empty();) {
		//nod = *PQ.begin(); PQ.erase(PQ.begin()); C--;
		nod = PQ.top(); PQ.pop(); C--;
		if(!C) {
			cout << nod.cost << endl;
			break;
		}
		auto &V = nod.V;
		chk.reset();
		for(int v : V) chk[v] = true;
		NOD nxt;

		for(int i = 0; i < K; i++) {
			int bf = V[i];
			chk[bf] = false;

			for(int j = 0; j < K; j++) {
				int mxi = N;
				for(int v : V) upmin(mxi, RO[j][v]);
				for(int c; mxi < N; mxi++) {
					c = O[j][mxi];
					if(chk[c]) continue;
					V[i] = c;
					nxt.f(V);
					cal(nxt);
					V[i] = bf;

					auto it = CMP.find(nxt.key);
					if(CMP.end() == it) {
						CMP.insert(nxt.key);
						PQ.push(nxt);
						break;
					}
				}
			}

			chk[bf] = true;
		}
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 1108 KB Output is correct
2 Correct 106 ms 1108 KB Output is correct
3 Correct 158 ms 1104 KB Output is correct
4 Correct 202 ms 1120 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 5708 KB Output is correct
2 Correct 220 ms 5512 KB Output is correct
3 Correct 209 ms 5504 KB Output is correct
4 Correct 212 ms 5608 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10640 KB Output is correct
2 Correct 567 ms 10584 KB Output is correct
3 Correct 440 ms 10500 KB Output is correct
4 Correct 669 ms 7896 KB Output is correct
5 Correct 962 ms 7580 KB Output is correct
6 Correct 164 ms 2192 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 1108 KB Output is correct
2 Correct 106 ms 1108 KB Output is correct
3 Correct 158 ms 1104 KB Output is correct
4 Correct 202 ms 1120 KB Output is correct
5 Correct 194 ms 5708 KB Output is correct
6 Correct 220 ms 5512 KB Output is correct
7 Correct 209 ms 5504 KB Output is correct
8 Correct 212 ms 5608 KB Output is correct
9 Correct 113 ms 10640 KB Output is correct
10 Correct 567 ms 10584 KB Output is correct
11 Correct 440 ms 10500 KB Output is correct
12 Correct 669 ms 7896 KB Output is correct
13 Correct 962 ms 7580 KB Output is correct
14 Correct 164 ms 2192 KB Output is correct
15 Correct 96 ms 10512 KB Output is correct
16 Correct 775 ms 7576 KB Output is correct
17 Correct 900 ms 7680 KB Output is correct
18 Correct 215 ms 10764 KB Output is correct
19 Correct 574 ms 10832 KB Output is correct