oj.uz

답안 #958748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958748 2024-04-06T13:54:24 Z gs25 Olympiads (BOI19_olympiads) C++17
0 / 100
 32 ms 1944 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 32 ms 1944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -