Submission #800932

#TimeUsernameProblemLanguageResultExecution timeMemory
800932andecaandeciKitchen (BOI19_kitchen)C++17
100 / 100
19 ms664 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 3e2 + 5;

int a[N], b[N], dp[N * N];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int n, m, k, sum1 = 0, sum2 = 0;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] < k) {
      cout << "Impossible\n";
      return 0;
    }
    sum1 += a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    sum2 += b[i];
  }
  for (int i = 1; i <= sum2; i++) dp[i] = -1e9;
  for (int i = 1; i <= m; i++) {
    for (int j = sum2; j >= b[i]; j--) dp[j] = max(dp[j], dp[j - b[i]] + min(b[i], n));
  }
  for (int i = sum1; i <= sum2; i++) {
    if (dp[i] >= n * k) {
      cout << i - sum1 << "\n";
      return 0;
    }
  }
  cout << "Impossible\n";
}
#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...