Submission #1305845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305845		DanielPr8	Olympiads (BOI19_olympiads)	C++20	0 / 100	2101 ms	191828 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using vvv = vector<vvl>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
vvl pr;
ll C, n, k, kw;
vvl vec;
vll las(1e6);
map<pll,ll> chil;
vpl cmf;
ll cur=0;
ll calc(ll p, ll wh){
    ll ans=0;
    for(ll i = 0; i < k; ++i){
        if(wh&(1<<i))ans += vec[p][i];
    }
    return ans;
}
ll mx(ll p, ll q, ll wh){
    ll ans=0;
    for(ll i = 0; i < k; ++i){
        if(wh&(1<<i))ans += max(vec[p][i],vec[q][i]);
    }
    return ans;
}

vll merge(vll a, vll b, ll wh){
    cur++;
    vll ans;
    for(ll i=0, j=0;ans.size()<C && (i<a.size() || j<b.size());){
        ll o=0;
        if(i==a.size())o=1;
        else if(j<b.size() && calc(b[j],wh)>calc(a[i],wh))o=1;
        if(!o){
            if(las[a[i]]!=cur){
                ans.pb(a[i]);
                las[a[i]]=cur;
            }
            i++;
        }
        else{
            if(las[b[j]]!=cur){
                ans.pb(b[j]);
                las[b[j]]=cur;
            }
            j++;
        }
    }
    return ans;
}
ll cre(ll a, ll b){
    if(a>b)swap(a,b);
    if(chil.count({a,b}))return chil[{a,b}];
    cmf.pb({a,b});
    // las.pb(0);
    chil[{a,b}]=vec.size();
    vec.pb(vec[a]);
    for(ll i = 0; i < k; ++i){
        vec.back()[i]=max(vec[a][i],vec[b][i]);
    }
    return vec.size()-1;
}
vll adup(vll a, vll b, ll wh){
    vll ans;
    if(a.empty() || b.empty())return ans;
    cur++;
    priority_queue<pair<ll,pll>> pq;
    for(ll i = 0; i < a.size(); ++i)pq.push({mx(a[i],b[0], wh), {i,0}});
    while(!pq.empty() && ans.size()<C){
        auto [sm, o]=pq.top();pq.pop();
        ll nw = cre(a[o.f],b[o.s]);
        if(nw!=-1){
            ans.pb(nw);
        }
        if(o.s+1<b.size())pq.push({mx(a[o.f],b[o.s+1], wh), {o.f,o.s+1}});
    }
    sort(all(ans),[&](ll i, ll j){
        return calc(i,wh)>calc(j,wh);
    });
    return ans;
}
vvl dev(vvl a, vvl b){
    vvl ans(kw);
    for(ll i = 0; i < kw; ++i){
        for(ll j = i; j >= 0; j= (j-1)&i){
            ans[i] = merge(ans[i], adup(a[j], b[i^j], i), i);
            if(j==0)break;
        }
    }
    return ans;
}
vvl supmer(vvl a, vvl b){
    vvl ans(kw);
    for(ll i = 0; i < kw; ++i){
        ans[i] = merge(a[i],b[i],i);
    }
    return ans;
}
vvv comb(vvv a, vvv b){
    vvv ans(k+1,vvl(kw));
    for(ll i = 0; i <= k; ++i){
        for(ll j = 0; j <= i; ++j){
            ans[i] = supmer(ans[i], dev(a[j],b[i-j]));
        }
    }
    return ans;
}
vvl solve(ll i, ll le, vll mx, ll r){
    if(le==0)return {mx};
    if(i==r)return {};
    vvl ans = solve(i+1, le, mx, r);
    for(ll j = 0; j < k; ++j)mx[j]=max(mx[j],pr[i][j]);
    vvl tr = solve(i+1, le-1, mx, r);
    for(auto i:tr)ans.pb(i);
    return ans;
}

vvv alps(ll l, ll r){
    vvv ans(k+1, vvl(kw));
    ans[0]=vvl(kw, vll(1,0));
    for(ll i = 1; i <= k; ++i){
        vvl al = solve(l, i, vll(k), r);
        vll op;
        for(ll j = 0; j < al.size(); ++j){
            op.pb(vec.size());
            cmf.pb({vec.size(),vec.size()});
            vec.pb(al[j]);
        }
        for(ll j = 0; j < kw; ++j){
            sort(all(op),[&](ll x, ll y){
                return calc(x,j)>calc(y,j);
            });
            ans[i][j]=op;
            if(op.size()>=C)ans[i][j].resize(C);
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    cin >> n >> k >> C;
    kw=(1<<k);
    pr = vvl(n, vll(k));
    for(auto& i:pr){
        for(auto& j:i){
            cin >> j;
        }
    }
    vec.pb(vll(k));
    cmf.pb({0,0});
    chil[{0,0}]=0;
    las.pb(0);
    vvv ans(k+1, vvl(kw));
    ans[0]=vvl(kw,vll(1,0));
    ll t = 1;
    for(ll i = 0; i < n; i += t){
        vvv nex = alps(i, min(n,i+t));
        ans = comb(ans, nex);
    }
    cout << calc(ans[k][kw-1].back(), kw-1);
}

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