Submission #281952

#TimeUsernameProblemLanguageResultExecution timeMemory
281952BlagojceOlympiads (BOI19_olympiads)C++11
0 / 100
49 ms24084 KiB
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(v) begin(v), end(v)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

ll const inf = 1e18;
ld const eps = 1e-13;
int const i_inf = 1e9;
int const mxn = 500;

mt19937 _rand(time(NULL));
clock_t _timer = clock();

int n, k, c;
int a[mxn][6];

int state[100000][mxn];

int find_subopt(int space){
	bool c[k];
	memset(c, false, sizeof(c));
	
	fr(i, 0, n){
		if(state[space][i] > 0){
			c[state[space][i]-1] = true;
		}
	}
	fr(j, 0, k){
		if(c[j]) continue;
		
		int pos, mx = -1;
		fr(i, 0, n){
			if(state[space][i] != 0) continue;
			
			if(a[i][j] > mx){
				mx = a[i][j];
				pos = i;
			}
		}
		if(mx == -1) return -1;
		
		state[space][pos] = j+1;
	}
	int ans[k];
	memset(ans, 0, sizeof(ans));
	fr(i, 0, n){
		if(state[space][i] > 0){
			fr(j, 0, k){
				ans[j] = max(ans[j], a[i][j]);
			}
		}
	}
	int ret = 0;
	fr(j, 0, k) ret += ans[j];
	return ret;
}

pq <pii> Q;
int nod;
void divide_space(int space){
	int c[k];
	fr(i, 0, n){
		if(state[space][i] > 0){
			c[state[space][i]-1] = i;
		}
	}
	fr(i, 0, k){
		fr(j, 0, n) state[nod][j] = state[space][j];
		
		fr(j, 0, i){
			state[nod][c[j]] = j+1;
		}
		state[nod][c[i]] = -1;
		Q.push({find_subopt(nod), nod});
		nod++;
	}
}
int fsearch(){
	Q.push({find_subopt(nod), nod});
	nod++;
	
	int proc = 0;
	while(!Q.empty()){
		int res = Q.top().st, u = Q.top().nd;
		proc ++; 
		Q.pop();
		if(proc == c){
			return res;
		}
		divide_space(u);
	}
	return -1;
}

void solve(){
	cin >> n >> k >> c;
	fr(i, 0, n){
		fr(j, 0, k){
			cin >> a[i][j];
		}
	}
	cout<<fsearch()<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...