Submission #1305842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305842		DanielPr8	Olympiads (BOI19_olympiads)	C++20	13 / 100	2097 ms	46812 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;
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;
}

vll merge(vll a, vll b, ll wh){
    if(wh+1==kw){
        cout << "";
    }
    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){
            ans.pb(a[i]);
            i++;
        }
        else{
            ans.pb(b[j]);
            j++;
        }
    }
    return ans;
}
void rt(ll j, vll v){
    for(ll i = 0; i < k; ++i)v[i] = max(v[i], vec[j][i]);
    vec.pb(v);
    las.pb(0);
}
vvl ad(vvl tr, vll v){
    vvl ans(kw);
    cur++;
    vll op;
    for(auto i:tr){
        for(auto j:i){
            if(las[j]==cur)continue;
            las[j]=cur;
            op.pb(las.size());
            rt(j, v);
        }
    }
    for(ll i = 0; i < kw; ++i){
        ans[i] = op;
        sort(all(ans[i]), [&](ll a, ll b){
            return calc(a,i)>calc(b,i);
        });
        if(ans[i].size()>C)ans[i].resize(C);
    }
    return ans;
}
vector<vvv> dp;
void solve(ll i, ll le){
    if(!dp[i][le].empty())return;
    if(le==0){
        dp[i][le]=vvl(kw, vll(1,0));
        return;
    }
    if(i+le>n){
        dp[i][le]=vvl(kw);
        return;
    }
    solve(i+1, le);
    solve(i+1, le-1);
    dp[i][le]=ad(dp[i+1][le-1], pr[i]);
    for(ll j = 0; j < kw; ++j)dp[i][le][j]=merge(dp[i][le][j],dp[i+1][le][j], j);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    cin >> n >> k >> C;
    dp=vector<vvv>(n+1,vvv(k+1));
    kw=(1<<k);
    pr = vvl(n, vll(k));
    for(auto& i:pr){
        for(auto& j:i){
            cin >> j;
        }
    }
    vll v(k);
    vec.pb(v);
    las.pb(0);
    solve(0,k);
    vvl ret = ad(dp[0][k], v);
    cout << calc(ret[kw-1].back(),kw-1);
}

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