제출 #959426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959426		gs25	Olympiads (BOI19_olympiads)	C++17	0 / 100	65 ms	1920 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;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#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) / j;
			if (cnt > C) break; 
		}
		if (cnt > C) cnt = C;
	}

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

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

	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(tott,t.cnt);
		if (cntt >= C) {
			//dbg("wtf?");
			cout << tott; return 0;
		}
		//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));
		}
	}


}

컴파일 시 표준 에러 (stderr) 메시지

olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:143: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]
  143 |   for (int i = in1.size(); i < t.can.size(); i++) can.pb(t.can[i]);
      |                            ~~^~~~~~~~~~~~~~
olympiads.cpp:149:21: 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]
  149 |   for (int i = 0; i < can.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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