제출 #1309042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309042		Born_To_Laugh	Kitchen (BOI19_kitchen)	C++17	29 / 100	15 ms	1612 KiB

kitchen

// 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;
}

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