Submission #1226762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226762		nanaseyuzuki	Kitchen (BOI19_kitchen)	C++20	100 / 100	117 ms	222536 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair <int, int>

const int mn = 305, mm = (1 << 20) + 1, inf = 1e18;
int a[mn], f[mn], m, n, k, b[mn];
int dp[mn][mn * mn];

void solve(){
    cin >> n >> m >> k;
    int sum = 0, sum1 = 0, min_val = INT_MAX;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
        min_val = min(min_val, a[i]);
    }
    for(int i = 1; i <= m; i++){
        cin >> b[i];
        sum1 += b[i];
    }
    if(m < k || min_val < k || sum1 < sum){
        cout << "Impossible\n";
        return;
    }
    // cout << 1 << '\n';
    fill(&dp[0][0], &dp[0][0] + mn * mn * mn, -inf);
    dp[0][0] = 0;
    for(int i = 1; i <= m; i++){
        for(int j = 0; j <= sum1; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= b[i]){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(n, b[i]));
            }
        }
    }
    int res = INT_MAX;
    for(int j = max(sum, n * k); j <= sum1; j++){
        if(dp[m][j] >= n * k){
            res = j;
            break;
        }
    }
    if(res == INT_MAX) cout << "Impossible\n";
    else cout << res - sum;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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