Submission #128097

#	Time	Username	Problem	Language	Result	Execution time	Memory
128097		Harry464	Kitchen (BOI19_kitchen)	C++14	100 / 100	15 ms	760 KiB

kitchen

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, m ,k;
  cin >> n >> m >> k;
  int suma = 0;
  int mini = 1<<29;
  vector <int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
    mini = min(mini,a[i]);
    suma += a[i];
  }
  int sumb = 0;
  vector <int> b(m);
  for (int i = 0; i < m; i++){
    cin >> b[i];
  }
  if (mini < k){
      cout << "Impossible";
      return 0;
  }
  if (k > m){
    cout << "Impossible";
    return 0;
  }
 vector <int> dp(90001,-1*(1<<29));
 dp[0] = 0;
 for (int i = 0; i < m; i++){
   int dod = b[i];
   sumb += dod;
   for (int j = sumb; j >= 0; j--){
     dp[j+dod] = max(dp[j+dod], dp[j] + min(dod,n));
   }
 }
 for (int i = suma; i <= sumb; i++){
   //cout << dp[i] << endl;
   if (dp[i] >= n*k){
     cout << i - suma;
     return 0;
   }
 }
 cout << "Impossible";
}

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