Submission #701263

#	Time	Username	Problem	Language	Result	Execution time	Memory
701263		_martynas	Kitchen (BOI19_kitchen)	C++11	100 / 100	47 ms	1036 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

const int MXN = 305;

int n, m, k;
int dp[2*MXN*MXN];
int A[MXN], B[MXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) cin >> A[i];
    for(int i = 0; i < m; i++) cin >> B[i];
    for(int i = 0; i < n; i++) {
        if(A[i] < k) {
            cout << "Impossible\n";
            return 0;
        }
    }
    int sum = accumulate(A, A+n, 0);
    fill(dp, dp+2*MXN*MXN, -1e9);
    dp[0] = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 2*MXN*MXN-1; j >= B[i]; j--) {
            dp[j] = max(dp[j], dp[j-B[i]]+min(B[i], n));
        }
    }
    for(int i = sum; i < 2*MXN*MXN; i++) {
        if(dp[i] >= n*k) {
            cout << i-sum << "\n";
            return 0;
        }
    }
    cout << "Impossible\n";
    return 0;
}

/*



*/

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