Submission #1346522

#TimeUsernameProblemLanguageResultExecution timeMemory
1346522M_W_13Kitchen (BOI19_kitchen)C++20
0 / 100
11 ms804 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const int MAXN = 307;
const int INF = 1e9;
int dp[MAXN * MAXN];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    int a[n];
    int b[m];
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    sort(a, a + n);
    rep(i, MAXN * MAXN) dp[i] = -INF;
    dp[0] = 0;
    rep(i, m) {
        for (int j = MAXN * MAXN - 1; j >= b[i]; j--) {
            dp[j] = max(dp[j], dp[j - b[i]] + min(n, b[i]));
        }
    }
    int ans = INF;
    int s = 0;
    rep(i, n) s += a[i];
    for (int x = s; x < (MAXN * MAXN); x++) {
        if (dp[x] >= (k * n)) {
            ans = x;
            break;
        }
    }
    if (ans == INF || a[0]<k) cout << "impossible" << '\n';
    else cout << (ans - s) << '\n';
    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...