Submission #205736

#TimeUsernameProblemLanguageResultExecution timeMemory
205736ics0503Kitchen (BOI19_kitchen)C++17
100 / 100
162 ms28024 KiB
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> using namespace std; short D[313][91919]; vector<int>Q[313]; vector<int>V[91919]; int A[313], B[313], S[313], tmp[313]; bool simul(vector<int>B, int n, int k) { priority_queue<int>H; int bSum = 0; for (int v : B) H.push(v); for (int i = n; i >= 1; i--) { // int g = A[i] - k; for (int j = 0; j < k; j++) { tmp[j] = H.top() - 1; H.pop(); if (tmp[j] < 0) return false; } for (int j = 0; j < k; j++)H.push(tmp[j]); } return true; } bool sort_a(int a, int b) { return a < b; } int main() { int n, m, k, i, j, aSum = 0; scanf("%d%d%d", &n, &m, &k); for (i = 1; i <= n; i++) { scanf("%d", &A[i]), aSum += A[i]; if (A[i] < k) { puts("Impossible"); return 0; } } for (i = 1; i <= m; i++) scanf("%d", &B[i]); sort(A + 1, A + 1 + n); sort(B + 1, B + 1 + m, sort_a); for (i = 1; i <= m; i++)S[i] = S[i - 1] + B[i]; D[0][0] = 0; for (i = 1; i <= S[1]; i++)D[0][i] = -1; for (i = 1; i <= m; i++) { for (j = 0; j <= S[i]; j++) { D[i][j] = D[i - 1][j]; if (B[i] <= j && D[i - 1][j - B[i]] != -1) { if (D[i][j] == -1 || D[i][j] < D[i-1][j - B[i]] + 1) { D[i][j] = D[i - 1][j - B[i]] + 1; } } } for (j = S[i] + 1; j < S[i + 1]; j++)D[i][j] = -1; } int ans = -1; for (i = aSum; i <= S[m]; i++) for (int v = 1; v <= m; v++) if (D[v][i] >= k && V[i].empty()) { Q[D[v][i]].push_back(i); int now = i; for (j = v; j > 0; j--) { if (now >= B[j] && D[j][now] == D[j - 1][now - B[j]] + 1) { V[i].push_back(B[j]); now -= B[j]; } } if (simul(V[i], n, k)) { printf("%d\n", i - aSum); return 0; } } printf("Impossible"); return 0; }

Compilation message (stderr)

kitchen.cpp: In function 'bool simul(std::vector<int>, int, int)':
kitchen.cpp:13:6: warning: unused variable 'bSum' [-Wunused-variable]
  int bSum = 0;
      ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:55:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = -1;
      ^~~
kitchen.cpp:30:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k, i, j, aSum = 0; scanf("%d%d%d", &n, &m, &k);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]), aSum += A[i];
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
kitchen.cpp:38:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= m; i++) scanf("%d", &B[i]);
                           ~~~~~^~~~~~~~~~~~~
#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...