fork download
copy 
  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.     // DP: M개 재료로 만들 수 있는 모든 합 계산
  26.     for (int cnt = 1; cnt <= M; cnt++) {
  27.         dp[1].reset();
  28.         for (int i = 0; i < N; i++) {
  29.             dp[1] |= (dp[0] << T[i]);
  30.         }
  31.         dp[0] = dp[1];
  32.     }
  33.     possible = dp[0];
  34.  
  35.     // D를 set으로 빠른 조회용
  36.     unordered_set<long long> Dset(D, D + K);
  37.  
  38.     int ans = 0;
  39.     long long maxD = D[K-1];
  40.     long long sumLimit = MAX_SUM - 1;
  41.  
  42.     for (int F1 = 0; F1 + maxD <= sumLimit; F1++) {
  43.         bool ok = true;
  44.         // F1 + D[i] 모두 가능해야 함
  45.         for (int i = 0; i < K; i++) {
  46.             if (!possible[F1 + D[i]]) {
  47.                 ok = false;
  48.                 break;
  49.             }
  50.         }
  51.         if (!ok) continue;
  52.  
  53.         // F1과 D에 없는 값 차이 검증
  54.         for (int diff = 0; diff <= maxD; diff++) {
  55.             if (Dset.count(diff)) continue;
  56.             if (possible[F1 + diff]) {
  57.                 ok = false;
  58.                 break;
  59.             }
  60.         }
  61.         if (ok) ans++;
  62.     }
  63.  
  64.     cout << ans << "\n";
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2 3 2
1 3
0 2
stdout
copy 
3
https://ideone.com/lTPg97
language:
C++ (gcc 8.3)
created:
22 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!