oj.uz

Submission #124888

# Submission time Handle Problem Language Result Execution time Memory
124888 2019-07-04T05:29:29 Z 이온조(#3049) Olympiads (BOI19_olympiads) C++14
0 / 100
 2000 ms 217904 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<pii> S[7];
int N, C, A[509][7];

set<vector<int> > st;

vector<int> V;
void go(vector<bool> &chk, int lft, int idx) {
	if(idx == N+1) {
		if(lft) return;
		if(st.find(V) == st.end()) --C;
		st.insert(V);
		return;
	}
	if(chk[idx]) {
		V.push_back(idx);
		go(chk, lft, idx+1);
		V.pop_back();
	}
	else {
		if(lft) {
			V.push_back(idx);
			go(chk, lft - 1, idx + 1);
			V.pop_back();
		}
		go(chk, lft, idx + 1);
	}
}

int main() {
	int K; scanf("%d%d%d",&N,&K,&C);
	for(int i=1; i<=N; i++) {
		for(int j=0; j<K; j++) {
			scanf("%d",&A[i][j]);
			S[j].push_back({A[i][j], i});
		}
	}
	for(int i=0; i<K; i++) {
		sort(S[i].begin(), S[i].end());
		reverse(S[i].begin(), S[i].end());
	}
	int s = 0;
	for(int i=0; i<K; i++) s += S[i][0].first;
	priority_queue<pair<int, vector<int> > > pq;
	pq.push({s, {0, 0, 0, 0, 0, 0}});
	while(pq.size()) {
		int sum, ns = 0; vector<int> T;
		tie(sum, T) = pq.top(); pq.pop();

		for(int i=0; i<K; i++) {
			vector<int> X = T;
			if(T[i] + 1 < N) {
				++X[i];
				pq.push({sum - S[i][T[i]].first + S[i][T[i] + 1].first, X});
			}
		}

		vector<bool> chk(N+1, 0); int Z = 0;
		for(int i=0; i<K; i++) chk[S[i][T[i]].second] = 1;
		for(int i=1; i<=N; i++) if(chk[i]) ++Z;

		V = vector<int>();
		go(chk, K-Z, 1);
		if(C <= 0) return !printf("%d", sum);
	}
	return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:50:12: warning: unused variable 'ns' [-Wunused-variable]
   int sum, ns = 0; vector<int> T;
            ^~
olympiads.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int K; scanf("%d%d%d",&N,&K,&C);
         ~~~~~^~~~~~~~~~~~~~~~~~~
olympiads.cpp:37:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 32332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 15268 KB Output is correct
2 Execution timed out 2071 ms 217904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 628 KB Output is correct
2 Execution timed out 2059 ms 90572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 32332 KB Time limit exceeded
2 Halted 0 ms 0 KB -