fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(0);
  7.  
  8.     int N, M, K;
  9.     cin >> N >> M >> K;
  10.     vector<int> T(N);
  11.     int maxT = 0;
  12.     for(int i = 0; i < N; i++) {
  13.         cin >> T[i];
  14.         maxT = max(maxT, T[i]);
  15.     }
  16.  
  17.     vector<int> D(K);
  18.     int Dmax = 0;
  19.     for(int i = 0; i < K; i++) {
  20.         cin >> D[i];
  21.         Dmax = max(Dmax, D[i]);
  22.     }
  23.  
  24.     int sum_limit = M * maxT; // 최대 합
  25.     vector<bool> dp(sum_limit + 1, false);
  26.     dp[0] = true;
  27.  
  28.     // DP: M개 선택 조합
  29.     for(int cnt = 0; cnt < M; cnt++) {
  30.         vector<bool> next(sum_limit + 1, false);
  31.         for(int s = 0; s <= sum_limit; s++) {
  32.             if(!dp[s]) continue;
  33.             for(int i = 0; i < N; i++) {
  34.                 if(s + T[i] <= sum_limit) next[s + T[i]] = true;
  35.             }
  36.         }
  37.         dp.swap(next);
  38.     }
  39.  
  40.     // D set
  41.     unordered_set<int> Dset(D.begin(), D.end());
  42.  
  43.     int ans = 0;
  44.     // F1 후보
  45.     for(int F1 = 0; F1 + Dmax <= sum_limit; F1++) {
  46.         bool ok = true;
  47.         // 모든 F1 + D[i] 가능해야 함
  48.         for(int i = 0; i < K; i++) {
  49.             if(!dp[F1 + D[i]]) { ok = false; break; }
  50.         }
  51.         if(!ok) continue;
  52.         // D에 없는 값은 만들 수 없어야 함
  53.         for(int x = 0; x <= Dmax; x++) {
  54.             if(Dset.count(x)) continue;
  55.             if(F1 + x <= sum_limit && dp[F1 + x]) { ok = false; break; }
  56.         }
  57.         if(ok) ans++;
  58.     }
  59.  
  60.     cout << ans << "\n";
  61. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
2 3 2
1 3
0 2
stdout
copy 
3
https://ideone.com/9XboQm
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!