Submission #128097

#TimeUsernameProblemLanguageResultExecution timeMemory
128097Harry464Kitchen (BOI19_kitchen)C++14
100 / 100
15 ms760 KiB
#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";
}
#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...