Submission #175901

#	Time	Username	Problem	Language	Result	Execution time	Memory
175901		AlexLuchianov	Kitchen (BOI19_kitchen)	C++14	100 / 100	162 ms	3348 KiB

kitchen

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 300;
int const inf = 1000000000;

int v[5 + nmax], v2[5 + nmax];
bitset<5 + nmax * nmax> dpinit, dp[5 + nmax];
int dist[5 + nmax * nmax];

int main()
{
  int n, k, m;
  cin >> n >> m >> k;
  int sum = 0;
  for(int i = 1;i <= n; i++) {
    cin >> v[i];
    sum += v[i];
    if(v[i] < k) {
      cout << "Impossible";
      return 0;
    }
  }
  dpinit[0] = 1;
  int ptr = 0;
  dp[0][0] = 1;
  for(int i = 1;i <= m; i++) {
    cin >> v2[i];
    if(v2[i] < n)
      dpinit |= (dpinit<<v2[i]);
    else{
      for(int j = ptr; 0 <= j; j--)
        dp[j + 1] |= (dp[j]<<v2[i]);
      ++ptr;
    }
  }
  dist[n * nmax + 1] = inf;
  for(int i = n * nmax; 0 <= i; i--){
    if(dpinit[i] == 1)
      dist[i] = 0;
    else
      dist[i] = dist[i + 1] + 1;
  }

  int result = inf;
  for(int i = 0; i <= ptr; i++){
    for(int j = 0; j <= i * nmax; j++){
      if(dp[i][j] == 1){
        int diff = MAX(n * k - i * n, sum - j);
        if(diff <= 0)
          result = MIN(result, j - sum);
        else
          result = MIN(result, dist[diff] + diff + j - sum);
      }
    }
  }

  if(1 + nmax * nmax <= result)
    cout << "Impossible";
  else
    cout << result;
  return 0;
}

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