Submission #1191320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191320		AlgorithmWarrior	Kitchen (BOI19_kitchen)	C++20	50 / 100	205 ms	114964 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=305;
bitset<MAX*MAX>dp1[MAX];
bitset<MAX*MAX>dp2[MAX];
int n,m,k;
int a[MAX],b[MAX];
int summin[MAX][MAX*MAX];
int cnt1,cnt2;
int sum1,sum2;

void add(bitset<MAX*MAX>dp[],int val,int cap){
    int i;
    for(i=cap;i;--i)
        dp[i]|=(dp[i-1]<<val);
}

void read(){
    cin>>n>>m>>k;
    int i;
    for(i=1;i<=n;++i)
        cin>>a[i];
    for(i=1;i<=m;++i)
        cin>>b[i];
}

bool check(){
    if(m<k)
        return 0;
    int i;
    for(i=1;i<=n;++i){
        if(a[i]<k)
            return 0;
        sum1+=a[i];
    }
    for(i=1;i<=m;++i)
        sum2+=b[i];
    if(sum1>sum2)
        return 0;
    return 1;
}

void create_knapsacks(){
    dp1[0][0]=1;
    dp2[0][0]=1;
    int i;
    for(i=1;i<=m;++i)
        if(b[i]>=n){
            ++cnt1;
            add(dp1,b[i],cnt1);
        }
        else{
            ++cnt2;
            add(dp2,b[i],cnt2);
        }
}

void create_summin(){
    int i,j;
    for(i=MAX-1;i>=0;--i)
        for(j=MAX*MAX-1;j>=0;--j){
            if(i==MAX-1 || j==MAX*MAX-1){
                summin[i][j]=INF;
                continue;
            }
            if(dp2[i][j])
                summin[i][j]=j;
            else
                summin[i][j]=min(summin[i+1][j],summin[i][j+1]);
        }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int solve(){
    int ans=INF;
    int i,j;
    for(i=0;i<=cnt1;++i)
        for(j=0;j<=sum2;++j)
            if(dp1[i][j]){
                int nrc=max(0,k-i);
                int sum=max(0,max(sum1-j,(k-i)*n));
                minself(ans,j+summin[nrc][sum]-sum1);
            }
    return ans;
}

int main()
{
    read();
    if(!check()){
        cout<<"Impossible";
        return 0;
    }
    create_knapsacks();
    create_summin();
    cout<<solve();
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 28