| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1326964 | DeathIsAwe | Olympiads (BOI19_olympiads) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int n, k, c;
vector<vector<int>> scores;
vector<ll> order[6000001];
ll pownum(int a, int b) {
ll bruh = 1;
for (int i=0;i<b;i++) bruh *= (ll)a;
return bruh;
}
ll convert(vector<int> bruh) {
sort(bruh.begin(), bruh.end());
ll sus = 0;
for (int i=0;i<k;i++) sus += bruh[i] * pownum(1000, i);
return sus;
}
vector<int> revconvert(ll bruh) {
vector<int> asdf;
for (int i=0;i<k;i++) {
asdf.pb(bruh % 1000);
bruh /= 1000;
}
return asdf;
}
int totalscore(vector<int> bruh) {
vector<int> valvec(k, 0);
for (int i=0;i<k;i++) for (int j=0;j<k;j++) valvec[i] = max(valvec[i], scores[bruh[j]][i]);
int valnum = 0;
for (int i=0;i<k;i++) valnum += valvec[i];
return valnum;
}
int main() {
cin >> n >> k >> c;
scores = vector<vector<int>>(n, vector<int> (k));
for (int i=0;i<n;i++) for (int j=0;j<k;j++) cin >> scores[i][j];
vector<int> maxvec(k, 0);
for (int i=0;i<n;i++) for (int j=0;j<k;j++) maxvec[j] = max(maxvec[j], scores[i][j]);
vector<int> notchosen, chosen;
vector<bool> ismax(k, false);
for (int i=0;i<n;i++) {
int flag = -1;
for (int j=0;j<k;j++) if (!ismax[j] && (maxvec[j] == scores[i][j])) {flag = j; break;}
if (flag == -1) {
notchosen.pb(i);
} else {
for (int j=0;j<k;j++) if (maxvec[j] == scores[i][j]) ismax[j] = true;
chosen.pb(i);
}
}
while (chosen.size() != k) {
chosen.pb(notchosen[notchosen.size() - 1]);
notchosen.pop_back();
}
chosen.pb(0);
chosen[k] = totalscore(chosen);
pair<int,ll> chosenpair = mp(totalscore(chosen), convert(chosen));
order[chosenpair.ff].pb(chosenpair.ss);
unordered_set<ll> tobevis; tobevis.insert(chosenpair.ss);
int count = 0, mintotal = chosenpair.ff;
vector<bool> curvals(n, false);
ll toppair, dumbruhval;
vector<int> bruh, dumbruh, curmax;
int curtotalscore, tempcurtotal;
bool ans = false;
for (int curscore=chosenpair.ff;curscore>-1;curscore--) {
while (order[curscore].size() > 0) {
toppair = order[curscore][order[curscore].size() - 1]; order[curscore].pop_back();
bruh = revconvert(toppair);
for (int i=0;i<k;i++) curvals[bruh[i]] = true;
dumbruh = bruh;
for (int i=0;i<k;i++) {
curmax = vector<int>(6, 0);
for (int j=0;j<k;j++) {
for (int l=0;l<k;l++) {
if (l == i) continue;
curmax[j] = max(curmax[j], scores[bruh[l]][j]);
}
}
curtotalscore = 0;
for (int j=0;j<k;j++) curtotalscore += curmax[j];
for (int j=0;j<n;j++) {
dumbruh[i] = j;
dumbruhval = convert(dumbruh);
if (!curvals[j] && tobevis.find(dumbruhval) == tobevis.end()) {
tempcurtotal = curtotalscore;
for (int l=0;l<k;l++) tempcurtotal += max(0, scores[dumbruh[i]][l] - curmax[l]);
if (tempcurtotal > mintotal || tobevis.size() < c) {
order[tempcurtotal].pb(dumbruhval);
tobevis.insert(dumbruhval);
mintotal = min(mintotal, tempcurtotal);
}
}
dumbruh[i] = bruh[i];
}
}
count += 1;
if (count == c) {
cout << curscore;
ans = true;
break;
}
for (int i=0;i<k;i++) curvals[bruh[i]] = false;
}
if (ans) break;
}
}