Submission #1342906

#TimeUsernameProblemLanguageResultExecution timeMemory
1342906Jakub_WozniakKitchen (BOI19_kitchen)C++20
20 / 100
62 ms448 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 309;
const int maxA = maxn*maxn+9;
bitset<maxA> dp;
int A[maxn] , B[maxn];

void nie()
{
    cout << "Impossible\n";
    exit(0);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N ,  K , M;
    cin >> N >> M >> K;

    if(K > M)nie();

    for(int i = 0 ; i < N ; i++)cin >> A[i];
    for(int i = 0 ; i < N ; i++)
    {
        if(A[i] < K)nie();
    }
    for(int i = 0 ; i < M ; i++)cin >> B[i];

    dp[0] = 1;
    for(int i = 0 ; i < M ; i++)
    {
        for(int j = maxA-1 ; j >= B[i]; j--)dp[j] = (dp[j] | (dp[j-B[i]]));
    }

    int S = 0;
    for(int i =0 ; i < N ; i++)S += A[i];

    for(int i = S ; i < maxA ; i++)
    {
        if(dp[i])
        {
            cout << i-S << '\n';
            exit(0);
        }
    }

    nie();



    return 0;
}
#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...