Submission #958748

#	Time	Username	Problem	Language	Result	Execution time	Memory
958748		gs25	Olympiads (BOI19_olympiads)	C++17	0 / 100	32 ms	1944 KiB

olympiads

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll; 


#define int ll 

int N, K, C;
vector<vector<int>> v;



struct fuck {
	vector<int> in;
	vector<bool> out;
	vector<int> can;
	int cnt = 0;
	int tot = 0;

	fuck(vector<int>& in1, vector<bool>& out1) {
		in = in1;
		out = out1;
		solve();
	}

	void solve() {
		for (auto x : in) can.pb(x);
		for (int i = 0; i < K; i++) {
			int Midx = 0, Mval = -1;
			for (auto id : can) {
				if (v[id][i] > Mval) {
					Midx = id;
					Mval = v[id][i];
				}
			}
			rep(j, N) {
				if (!out[j] && v[j][i] > Mval) {
					Midx = j;
					Mval = v[j][i];
				}
			}
			tot += Mval;
			can.pb(Midx);
		}
		sort(all(can));
		can.erase(unique(all(can)), can.end());
		int u = can.size();
		int l = 0;
		rep(i, N) l += (int)out[i];
		cnt = 1;
		for (int j = 1; j <= K - u; j++) {
			cnt = cnt * (N + 1 - u - l - j) / (K - u);
			if (cnt > C) break;
		}
	}

	bool operator <(const fuck& ot) const {
		return tot < ot.tot;
	}
};


void solve() {
	cin >> N >> K >> C;
	rep(i, N) {
		vector<int> tmp;
		rep(i, K) {
			int x; cin >> x; tmp.pb(x);
		}
		v.pb(tmp);
	}
	vector<bool> a(N);
	vector<int> b;
	int cntt = 0, tott = 0;
	priority_queue<fuck> pq;
	fuck st(b, a);
	pq.push(st);
	while (!pq.empty()) {
		fuck t = pq.top();
		pq.pop();
		tott = t.tot;
		cntt += t.cnt;
		//dbg(tot,cnt);
		if (cntt >= C) {
			//dbg("wtf?");
			cout << tott; return;
		}
		//vector<int> can = t.can;
		vector<int> in1 = t.in;
		vector<int> can; 
		for (int i = in1.size(); i < t.can.size(); i++) can.pb(t.can[i]); 
		vector<bool> out = t.out;

		int shit = N; 
		rep(i, N) shit -= out[i];
		if (shit < K + 1) continue; 
 		for (int i = 0; i < can.size(); i++) {
			out[can[i]] = 1; 
			if (i >= 1) out[can[i - 1]] = 0; 
			if(i>=1)in1.pb(can[i-1]);
			pq.push(fuck(in1, out));
		}
	}
}

int32_t main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t = 1; //cin >> t; 
	while (t--) solve();


}

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:97:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = in1.size(); i < t.can.size(); i++) can.pb(t.can[i]);
      |                            ~~^~~~~~~~~~~~~~
olympiads.cpp:103:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for (int i = 0; i < can.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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