Submission #281939

#	Time	Username	Problem	Language	Result	Execution time	Memory
281939		Blagojce	Olympiads (BOI19_olympiads)	C++11	0 / 100	67 ms	24104 KiB

olympiads

#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));
	
	int ret = 0;
	fr(i, 0, n){
		if(state[space][i] > 0){
			c[state[space][i]-1] = true;
			ret += a[i][state[space][i]-1];
		}
	}
	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;
			}
		}
		state[space][pos] = j+1;
		ret += mx;
	}
	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, 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();
}

Compilation message (stderr)

olympiads.cpp: In function 'int find_subopt(int)':
olympiads.cpp:49:21: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   state[space][pos] = j+1;
      |   ~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32