oj.uz

Submission #757805

# Submission time Handle Problem Language Result Execution time Memory
757805 2023-06-13T18:40:12 Z taher Kitchen (BOI19_kitchen) C++17
72 / 100
 1000 ms 11212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
using namespace std;
 
const int N = 300 * 300 + 5;
bool visited[305][N];
int ndp[N];

const int maxN = 305;
int a[maxN], b[maxN], long_ids[maxN], short_ids[maxN];
 
const int inf = 1000000000;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  bool found = false;
  int n, m, k;
  cin >> n >> m >> k;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    tot += a[i];
    if (a[i] < k) {
      found = true;
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }

  int ans = inf;

  if (!found) {
    int ptr_long = 0, ptr_short = 0;

    for (int i = 0; i < m; i++) {
      if (b[i] >= n) {
        long_ids[ptr_long++] = i;
      } else {
        short_ids[ptr_short++] = i;
      }
    }
   
    ndp[0] = 1;
    for (int i = 0; i < ptr_long; i++) {
      for (int it = N - 1 - b[long_ids[i]]; it >= 0; it--) {
        if (ndp[it] > 0) {
          ndp[it + b[long_ids[i]]] = max(ndp[it + b[long_ids[i]]], ndp[it] + 1);
        }
      }
    }
    for (int i = 0; i < N; i++) {
      if (ndp[i] > 0) --ndp[i];
    }

    function<void(int, int)> Rec = [&](int i, int sum) {
      if (visited[i][sum]) {
        return ;
      }
      if (i == ptr_short) {
        if (sum >= max(n * k, tot)) {
          ans = min(ans, sum - tot);
          return ;
        }
        int ptr = tot - sum;
        while (ptr < N && sum + n * ndp[ptr] < n * k) ptr++;
        if (ptr < N && ndp[ptr] > 0) {
          ans = min(ans, sum + ptr - tot);
        }
        return ;
      }
      Rec(i + 1, sum + b[short_ids[i]]);
      Rec(i + 1, sum);
      visited[i][sum] = true;
      return ;
    };
   
    Rec(0, 0);
  }

  if (ans < inf && !found) {
    cout << ans << '\n';
  } else {
    cout << "Impossible\n";
  }
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 16 ms 712 KB Output is correct
13 Correct 115 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10048 KB Output is correct
2 Correct 47 ms 7812 KB Output is correct
3 Correct 176 ms 8568 KB Output is correct
4 Correct 101 ms 5960 KB Output is correct
5 Correct 166 ms 11212 KB Output is correct
6 Correct 45 ms 6572 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 20 ms 724 KB Output is correct
3 Correct 80 ms 952 KB Output is correct
4 Correct 82 ms 728 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 16 ms 712 KB Output is correct
13 Correct 115 ms 724 KB Output is correct
14 Correct 83 ms 10048 KB Output is correct
15 Correct 47 ms 7812 KB Output is correct
16 Correct 176 ms 8568 KB Output is correct
17 Correct 101 ms 5960 KB Output is correct
18 Correct 166 ms 11212 KB Output is correct
19 Correct 45 ms 6572 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 20 ms 724 KB Output is correct
22 Correct 80 ms 952 KB Output is correct
23 Correct 82 ms 728 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 9 ms 596 KB Output is correct
26 Correct 12 ms 700 KB Output is correct
27 Correct 395 ms 1168 KB Output is correct
28 Correct 794 ms 2252 KB Output is correct
29 Correct 29 ms 580 KB Output is correct
30 Execution timed out 1071 ms 4304 KB Time limit exceeded
31 Halted 0 ms 0 KB -