Submission #129200

#	Time	Username	Problem	Language	Result	Execution time	Memory
129200		nikolapesic2802	Olympiads (BOI19_olympiads)	C++14	100 / 100	609 ms	10568 KiB

olympiads

////!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);
        _();
    }

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