////!pragma
//ll hsh(const vi &banned, bool zero = false){
// ll ans = 1-zero;
// for(int x : banned){
// ans <<= 9;
// ans |= x;
// }
// return ans;
//}
//void _(){
// int n,k,c;
// cin >> n >> k >> c;
// vvi arr(n,vi(k));
// cin >> arr;
// priority_queue<vi> pq;
// vi init(k+2,0); //sum,sz,arr,nxt
// pq.push(vi(init));
// vi sums;
// vi opt(k);
// for(int i = 0; i < n; ++i)
// for(int j = 0; j < k; ++j)
// opt[j] = max(opt[j],arr[i][j]);
// unordered_set<ll> seen;
// int total = 0, blocked = 0;
// vi opti;
// while(sz(sums) < c && !pq.empty()){
// vi cur = pq.top();
// pq.pop();
// if(cur[1] == k){
// sums.pb(cur[0]);
// continue;
// }
// vi banned = vi(cur.begin()+k+2,cur.end());
// cur.resize(k+2);
// ll lhsh = 1, rhsh = hsh(banned,true);
// ll shift = sz(banned)*9;
// int l = 0;
// for(int i = 0; i < n; ++i){
// if(l < sz(banned) && banned[l] == i){
// lhsh <<= 9;
// lhsh |= i;
// shift -= 9;
// rhsh = rhsh & ((1LL<<shift)-1);
// ++l;
// continue;
// }
// vi nxt = cur;
// for(int j = 0; j < k; ++j)
// nxt[j+2] = max(nxt[j+2],arr[i][j]);
// nxt[1] += 1;
// vi scores;
// nxt[0] = 0;
// for(int j = 2; j < 2+nxt[1]; ++j)
// nxt[0] += nxt[j]-opt[j-2];
// vi nbanned = banned;
// nbanned.insert(nbanned.begin()+l,i);
// nxt.insert(nxt.end(),all(nbanned));
// ++total;
// ll h = (((lhsh << 9) | i ) << shift) | rhsh;
// if(sz(opti) >= c && opti[c-1] >= nxt[0]){
// ++blocked;
// continue;
// }
// if(!seen.count(h)){
// if(nxt[1] == k){
// opti.pb(nxt[0]);
// if(sz(opti) == c)
// sort(rall(opti));
// else if(sz(opti) == 2*c){
// sort(rall(opti));
// opti.resize(c);
// }
// }
// seen.insert(h);
// pq.push(nxt);
// }
// }
// }
// //watch(total);
// //watch(blocked);
// //watch(sz(opti));
// print(sums[c-1]+sum(opt));
//}
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stack>
#include <unordered_set>
#include <set>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
for(T it = b; it != e; ++it)
stream >> *it;
return stream;
}
T1 void print(T x, string end = "\n"){
cout << x << end;
}
T1 T sum(vector<T>& arr){
T ans = 0;
for(auto x : arr)
ans += x;
return ans;
}
//!pragma
ll hsh(const vi &banned, bool zero = false){
ll ans = 1-zero;
for(int x : banned){
ans <<= 9;
ans |= x;
}
return ans;
}
void _(){
int n,k,c;
cin >> n >> k >> c;
vvi arr(n,vi(k));
cin >> arr;
priority_queue<vi> pq;
vi init(k+2,0); //sum,sz,arr,nxt
pq.push(vi(init));
vi sums;
vi opt(k);
for(int i = 0; i < n; ++i)
for(int j = 0; j < k; ++j)
opt[j] = max(opt[j],arr[i][j]);
unordered_set<ll> seen;
int total = 0, blocked = 0;
vi opti;
while(sz(sums) < c && !pq.empty()){
vi cur = pq.top();
pq.pop();
if(cur[1] == k){
sums.pb(cur[0]);
continue;
}
vi banned = vi(cur.begin()+k+2,cur.end());
cur.resize(k+2);
ll lhsh = 1, rhsh = hsh(banned,true);
ll shift = sz(banned)*9;
int l = 0;
for(int i = 0; i < n; ++i){
if(l < sz(banned) && banned[l] == i){
lhsh <<= 9;
lhsh |= i;
shift -= 9;
rhsh = rhsh & ((1LL<<shift)-1);
++l;
continue;
}
vi nxt = cur;
for(int j = 0; j < k; ++j)
nxt[j+2] = max(nxt[j+2],arr[i][j]);
nxt[1] += 1;
vi scores;
nxt[0] = 0;
for(int j = 2; j < 2+nxt[1]; ++j)
nxt[0] += nxt[j]-opt[j-2];
vi nbanned = banned;
nbanned.insert(nbanned.begin()+l,i);
nxt.insert(nxt.end(),all(nbanned));
++total;
ll h = (((lhsh << 9) | i ) << shift) | rhsh;
if(sz(opti) >= c && opti[c-1] >= nxt[0]){
++blocked;
continue;
}
if(!seen.count(h)){
if(nxt[1] == k){
opti.pb(nxt[0]);
if(sz(opti) == c)
sort(rall(opti));
else if(sz(opti) == 2*c){
sort(rall(opti));
opti.resize(c);
}
}
seen.insert(h);
pq.push(nxt);
}
}
}
//watch(total);
//watch(blocked);
//watch(sz(opti));
print(sums[c-1]+sum(opt));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
_();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1188 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
63 ms |
2484 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
32 ms |
1656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
760 KB |
Output is correct |
| 2 |
Correct |
10 ms |
760 KB |
Output is correct |
| 3 |
Correct |
311 ms |
2228 KB |
Output is correct |
| 4 |
Correct |
298 ms |
1684 KB |
Output is correct |
| 5 |
Correct |
368 ms |
2992 KB |
Output is correct |
| 6 |
Correct |
28 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1188 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| 5 |
Correct |
26 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
63 ms |
2484 KB |
Output is correct |
| 7 |
Correct |
44 ms |
1656 KB |
Output is correct |
| 8 |
Correct |
32 ms |
1656 KB |
Output is correct |
| 9 |
Correct |
9 ms |
760 KB |
Output is correct |
| 10 |
Correct |
10 ms |
760 KB |
Output is correct |
| 11 |
Correct |
311 ms |
2228 KB |
Output is correct |
| 12 |
Correct |
298 ms |
1684 KB |
Output is correct |
| 13 |
Correct |
368 ms |
2992 KB |
Output is correct |
| 14 |
Correct |
28 ms |
1116 KB |
Output is correct |
| 15 |
Correct |
103 ms |
4764 KB |
Output is correct |
| 16 |
Correct |
535 ms |
10568 KB |
Output is correct |
| 17 |
Correct |
609 ms |
4336 KB |
Output is correct |
| 18 |
Correct |
248 ms |
3376 KB |
Output is correct |
| 19 |
Correct |
10 ms |
816 KB |
Output is correct |
