fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_SUM = 1000000 + 10;
  5. const int MAX_M = 1000 + 5;
  6.  
  7. int N, M, K;
  8. int T[MAX_M];
  9. long long D[MAX_M];
  10.  
  11. bitset<MAX_SUM> dp[2]; // dp[0]: 이전, dp[1]: 현재
  12. bitset<MAX_SUM> possible; // M개 재료로 만들 수 있는 합
  13.  
  14. int main() {
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.  
  18.     cin >> N >> M >> K;
  19.     for (int i = 0; i < N; i++) cin >> T[i];
  20.     for (int i = 0; i < K; i++) cin >> D[i];
  21.  
  22.     dp[0].reset();
  23.     dp[0][0] = 1;
  24.  
  25.     int maxT = *max_element(T, T + N);
  26.     int maxSum = M * maxT;
  27.  
  28.     // DP: M개 재료로 만들 수 있는 모든 합 계산
  29.     for (int cnt = 1; cnt <= M; cnt++) {
  30.         dp[1].reset();
  31.         for (int i = 0; i < N; i++) {
  32.             dp[1] |= (dp[0] << T[i]);
  33.         }
  34.         dp[0] = dp[1];
  35.     }
  36.     possible = dp[0];
  37.  
  38.     unordered_set<long long> Dset(D, D + K);
  39.     long long maxD = D[K-1];
  40.  
  41.     int ans = 0;
  42.  
  43.     // F1 후보 범위 최적화: 0 ~ maxSum - maxD
  44.     for (int F1 = 0; F1 + maxD <= maxSum; F1++) {
  45.         bool ok = true;
  46.         for (int i = 0; i < K; i++) {
  47.             if (!possible[F1 + D[i]]) {
  48.                 ok = false;
  49.                 break;
  50.             }
  51.         }
  52.         if (!ok) continue;
  53.  
  54.         for (long long diff = 0; diff <= maxD; diff++) {
  55.             if (Dset.count(diff)) continue;
  56.             if (possible[F1 + diff]) {
  57.                 ok = false;
  58.                 break;
  59.             }
  60.         }
  61.  
  62.         if (ok) ans++;
  63.     }
  64.  
  65.     cout << ans << "\n";
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
2 3 2
1 3
0 2
stdout 
3
https://ideone.com/vfEax7
language:
C++ (gcc 8.3)
created:
23 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!