Submission #1338725

#TimeUsernameProblemLanguageResultExecution timeMemory
1338725ninstroyerKitchen (BOI19_kitchen)C++20
100 / 100
71 ms100344 KiB
#include<bits/stdc++.h>
using namespace std;

const int nx =  305, inf = 1e9;

int n,m,k,total,totalA,a[nx],b[nx],dp[nx][nx*nx];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++) cin>>a[i], totalA+=a[i];
    for(int i = 1; i <= m; i++) cin>>b[i], total+=b[i];
    for(int i = 0; i <= m; i++)  for(int j = 1; j <= total; j++) dp[i][j]=-inf;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= total; j++)
        {
            dp[i][j]=dp[i-1][j];
            if(b[i]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-b[i]]+min(b[i],n));
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(a[i] < k) return cout<<"Impossible", 0;
    }
    int res = -1;
    for(int i = totalA; i <= total; i++)
    {
        if(dp[m][i] >= n*k)
        {
            res = i-totalA;
            break;
        }
    }
    if(res==-1) cout<<"Impossible";
    else cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...