Submission #1225172

#TimeUsernameProblemLanguageResultExecution timeMemory
1225172nguynKitchen (BOI19_kitchen)C++20
100 / 100
16 ms584 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 305;
const int inf = 300 * 300;

int n, m, k;
int a[N];
int b[N];
int f[N * N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    int mn = 1e9;
    int suma = 0;
    int sumb = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        suma += a[i];
        mn = min(mn, a[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        sumb += b[i];
    }

    if (mn < k) {
        cout << "Impossible";
        return 0;
    }
    for (int i = 1; i <= inf; i++) f[i] = -inf;
    f[0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = sumb; j >= b[i]; j--) {
            f[j] = max(f[j], f[j - b[i]] + min(b[i], n));
        }
    }
    for (int i = suma; i <= inf; i++) {
        if (f[i] >= n * k) {
            cout << i - suma;
            return 0;
        }
    }
    cout << "Impossible";
}
#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...