oj.uz

Submission #860712

# Submission time Handle Problem Language Result Execution time Memory
860712 2023-10-14T00:50:39 Z NK_ Olympiads (BOI19_olympiads) C++17
44 / 100
 2000 ms 2628 KB 
// 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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1112 KB Output is correct
2 Correct 127 ms 1112 KB Output is correct
3 Correct 133 ms 1240 KB Output is correct
4 Correct 89 ms 1116 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2620 KB Output is correct
2 Correct 142 ms 2504 KB Output is correct
3 Correct 144 ms 2628 KB Output is correct
4 Correct 144 ms 2508 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2101 ms 2620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1112 KB Output is correct
2 Correct 127 ms 1112 KB Output is correct
3 Correct 133 ms 1240 KB Output is correct
4 Correct 89 ms 1116 KB Output is correct
5 Correct 146 ms 2620 KB Output is correct
6 Correct 142 ms 2504 KB Output is correct
7 Correct 144 ms 2628 KB Output is correct
8 Correct 144 ms 2508 KB Output is correct
9 Execution timed out 2101 ms 2620 KB Time limit exceeded
10 Halted 0 ms 0 KB -