Submission #1309042

#TimeUsernameProblemLanguageResultExecution timeMemory
1309042Born_To_LaughKitchen (BOI19_kitchen)C++17
29 / 100
15 ms1612 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
using namespace std;

const int MAX_W = 300005; 
const int INF = 1e9 + 7;

int n, m, k;
int dp[MAX_W];
void solve(){
    if(!(cin >> n >> m >> k)) return;
    
    long long sum_needed = 0;
    bool impossible = false;

    for(int i = 1; i <= n; ++i){
        int x; cin >> x;
        sum_needed += x;
        if(x < k) impossible = true;
    }

    vector<int> chefs(m);
    long long sum_capacity = 0;
    for(int i = 0; i < m; ++i){
        cin >> chefs[i];
        sum_capacity += chefs[i];
    }

    if(impossible || sum_capacity < sum_needed || m < k){
        cout << "Impossible\n";
        return;
    }

    fill(dp, dp + MAX_W, -INF);
    dp[0] = 0;

    int current_sum = 0;

    for(int time : chefs){
        for(int j = current_sum; j >= 0; --j){
            if(dp[j] != -INF){
                if(j + time < MAX_W){
                    dp[j + time] = max(dp[j + time], dp[j] + 1);
                }
            }
        }
        current_sum = min(current_sum + time, MAX_W - 1);
    }

    int limit = min((long long)MAX_W - 1, sum_capacity);
    
    for(int i = sum_needed; i <= limit; ++i){
        if(dp[i] >= k){
            cout << i - sum_needed << '\n';
            return;
        }
    }

    cout << "Impossible\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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...