Submission #1342919

#TimeUsernameProblemLanguageResultExecution timeMemory
1342919Jakub_WozniakKitchen (BOI19_kitchen)C++20
100 / 100
199 ms3676 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;
bitset<maxA> dp2[maxn];
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];

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

    sort(B+1,B+M+1);

    int P = 1; // pierwszy B wiekszy rowny od N
    while(P <= M && B[P] < N)P++;

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

    vector<int> seti;
    for(int j = maxA-1 ; j >= 0; j--)if(dp[j])seti.push_back(j);
    reverse(seti.begin() , seti.end()); 

    // dp[i] = suma i , oraz i/N pelnych rzedow do updt

    dp2[0][0] = 1;
    for(int i = P ; i <= M ; i++) // O(N)
    {
        for(int k = K+1 ; k >= 0 ; k--) // O(N)
        {
            dp2[k] = (dp2[k]|(dp2[max(0,k-1)] << B[i]));
        }
    }


    int mini = maxA+1234;
    for(int j = 0 ; j < maxA-1 ; j++)
    {
        for(int k = 0 ; k <= K ; k++)
        {
            if(dp2[k][j] == 0)continue;
            // suma j , k pelnych
            // K - k pelnych , Suma conajmiej S-j

            int minT = max(N*(K-k) , max(0,S-j));
            auto it = lower_bound(seti.begin() , seti.end() , minT);
            if(it == seti.end())continue;
            mini = min(j + *it , mini);
        }
    }

    
    if(mini == maxA+1234)nie();
    else cout << mini-S << '\n';




    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...