oj.uz

Submission #205743

# Submission time Handle Problem Language Result Execution time Memory
205743 2020-02-29T16:51:11 Z ics0503 Olympiads (BOI19_olympiads) C++17
100 / 100
 13 ms 1428 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;

long long C[515][7];
struct xy { int x, y; };
vector<xy>L[6];
bool sort_x(xy a, xy b) {
	if (a.x != b.x)return a.x > b.x;
	return a.y < b.y;
}

struct state {
	int v, a[6];
	bool operator <(const state p)const {
		return v < p.v;
	}
};
int n, k, c;
long long trans(int a[]) {
	long long res = 0;
	for (long long i = 0, j = 1; i < k; i++, j *= (n+1)) {
		res += j * a[i];
	}
	return res;
}
set<long long>ck;
set<long long>alreadyDone;
int cck[515], S[6], V[6], G[6], pnum;
int dfs(int dep) {
	if (dep == k - pnum) {
		long long g = 0;
		for (int i = 0; i < pnum; i++)V[i] = S[i];
		for (int i = pnum; i < k; i++)V[i] = G[i - pnum];
		sort(V, V + k);
		for (long long i = 0, j = 1; i < k; i++, j *= (n + 1)) g += V[i] * j;
		int ret = alreadyDone.find(g) == alreadyDone.end();
		alreadyDone.insert(g);
		return ret;
	}
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		if (cck[i])continue;
		G[dep] = i;
		ret += dfs(dep + 1);
	}
	return ret;
}
int main() {
	int i, j, sum = 0; scanf("%d%d%d", &n, &k, &c);
	for (i = 1; i <= n; i++) {
		for (j = 0; j < k; j++) {
			int v; scanf("%d", &v);
			L[j].push_back({ v,i });
		}
	}
	for (i = 0; i <= 500; i++) {
		C[i][0] = 1;
		for (j = 1; j <= 6 && j <= i; j++)C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}
	for (i = 0; i < k; i++)sort(L[i].begin(), L[i].end(), sort_x), sum+=L[i][0].x;
	priority_queue<state>H;
	H.push({ sum, {0,0,0,0,0,0} });
	int cnt = 0;
	while (!H.empty()) {
		state now = H.top(); H.pop();
		for (i = 0; i < k; i++) {
			int who = L[i][now.a[i]].y;
			S[i] = who;
			cck[who] = 1;
		}
		sort(S, S + k);
		pnum = unique(S, S + k) - S;
		for (i = 0; i < pnum; i++)V[i] = S[i];
		int nowv = pnum;
		for (i = pnum; nowv < k && i <= n; i++) {
			if (cck[i] == 0)V[nowv++] = i;
		}
		sort(V, V + k);
		long long ret = 0;
		for (i = 0, j = 1; i < k; i++, j *= (n + 1)) ret += V[i] * j;

		if (alreadyDone.find(ret) == alreadyDone.end()) {
			if (c <= C[n - pnum][k - pnum]) {
				printf("%d", now.v);
				return 0;
			}
			ret = dfs(0);
			cnt += ret;
			if (c <= cnt) {
				printf("%d", now.v);
				return 0;
			}
		}
		for (int g : S)cck[g] = 0;
		for (i = 0; i < k; i++) if (now.a[i] + 1 < n) {
			state nxt = now; nxt.a[i]++;
			nxt.v = now.v - (L[i][now.a[i]].x - L[i][nxt.a[i]].x);
			long long transv = trans(nxt.a);
			if (ck.find(transv) == ck.end()) {
				ck.insert(transv);
				H.push(nxt);
			}
		}

	}
	return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:53:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int i, j, sum = 0; scanf("%d%d%d", &n, &k, &c);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d", &v);
           ~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 13 ms 888 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 9 ms 888 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 13 ms 1428 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 9 ms 888 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 9 ms 888 KB Output is correct
14 Correct 13 ms 1428 KB Output is correct
15 Correct 9 ms 892 KB Output is correct
16 Correct 7 ms 632 KB Output is correct
17 Correct 10 ms 1400 KB Output is correct
18 Correct 10 ms 1144 KB Output is correct
19 Correct 5 ms 376 KB Output is correct