Submission #860712

#	Time	Username	Problem	Language	Result	Execution time	Memory
860712		NK_	Olympiads (BOI19_olympiads)	C++17	44 / 100	2101 ms	2628 KiB

olympiads

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
// template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const ll BIG = ll(7e15);
const int LG = 18;
const int nax = 505;

ll get() { return rand() * 1LL * rand(); };
ll rnd() { return ((get() % MOD) * 1LL * (rand() % 17) + (get() % MOD)) % BIG; };

using B = bitset<nax>;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, K, C; cin >> N >> K >> C;

	V<vi> A(N, vi(K)); for(auto& v : A) {
		for(auto& x : v) cin >> x;
	}
	

	vl H(N); for(auto& x : H) x = rnd();

	map<ll, int> IDX; IDX[0] = 0; int cur = 1;

	V<B> VIS;
	V<vi> X;
	vi S;

	VIS.pb(B()); X.pb(vi(K, 0)); S.pb(0);

	set<pl> T; T.insert(mp(0, 0));

	set<int> CUR;

	auto get = [&](ll h) {
		if (sz(CUR) == 0) { 
			CUR.insert(cur++); 
			while(sz(VIS) <= cur) VIS.emplace_back();
			while(sz(X) <= cur) X.emplace_back();
			while(sz(S) <= cur) S.emplace_back();
		}

		if (IDX.find(h) == IDX.end()) {
			IDX[h] = *begin(CUR);
			CUR.erase(begin(CUR)); 
		}

		return IDX[h];
	};

	for(int t = 0; t < K; t++) {
		set<pl> NT;
		for(auto& r : T) {
			// cout << "START" << endl;
			int id = get(r.s);
			// cout << r.s << " " << r.f << " => " << id << endl;

			for(int i = 0; i < N; i++) if (!VIS[id][i]) {
				// cout << i << endl;

				ll h = r.s ^ H[i];
				int nid = get(h);
				// cout << id << " " << nid << endl;

				B vis = VIS[id]; vis[i] = 1; 
				vi x = X[id]; for(int k = 0; k < K; k++) {
					x[k] = max(x[k], A[i][k]);
				}
				// cout << endl;
				int s = accumulate(begin(x), end(x), 0);

				// for(auto& v : x) cout << v << " ";
				// cout << nl;

				// assert(nid < sz(VIS));

				VIS[nid] = vis; X[nid] = x; S[nid] = s;
				NT.insert(mp(s, h));

				while (sz(NT) > C) {
					ll hsh = (*begin(NT)).s; NT.erase(begin(NT));
					int ID = get(hsh); IDX.erase(hsh);
					CUR.insert(ID);
				}
			}
		}	
		T.swap(NT);
	}	

	// for(auto& x : T) cout << x.f << nl;

	// while(sz(T) > C) T.erase(begin(T));

	cout << (*begin(T)).f << nl;

	

	

	



	exit(0-0);
} 	 

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