Submission #800932

#	Time	Username	Problem	Language	Result	Execution time	Memory
800932		andecaandeci	Kitchen (BOI19_kitchen)	C++17	100 / 100	19 ms	664 KiB

kitchen

#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";
}

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