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.     for(int i=0;i<N;i++) cin >> T[i];
  12.     vector<long long> D(K);
  13.     for(int i=0;i<K;i++) cin >> D[i];
  14.  
  15.     // Meet-in-the-middle: N/2
  16.     int n1 = N/2, n2 = N-n1;
  17.     vector<int> L(T.begin(), T.begin()+n1), R(T.begin()+n1, T.end());
  18.  
  19.     auto getSums = [&](vector<int>& arr) {
  20.         vector<unordered_set<int>> sums(M+1);
  21.         sums[0].insert(0);
  22.         for(int t: arr){
  23.             for(int cnt=M;cnt>=1;cnt--){
  24.                 for(auto x: sums[cnt-1])
  25.                     sums[cnt].insert(x+t);
  26.             }
  27.         }
  28.         return sums;
  29.     };
  30.  
  31.     auto sumsL = getSums(L);
  32.     auto sumsR = getSums(R);
  33.  
  34.     // 모든 M개 합 생성
  35.     set<int> allSums;
  36.     for(int i=0;i<=M;i++){
  37.         for(int l: sumsL[i]){
  38.             int rcnt = M-i;
  39.             if(rcnt<0 || rcnt>sumsR.size()-1) continue;
  40.             for(int r: sumsR[rcnt])
  41.                 allSums.insert(l+r);
  42.         }
  43.     }
  44.  
  45.     long long maxD = D.back(), minD = D[0]; // D[0]은 0
  46.     // D에서 F1 후보에 영향을 주는 값 미리 계산
  47.     set<long long> forbidden;
  48.     for(long long d: D) forbidden.insert(d);
  49.  
  50.     int ans=0;
  51.     for(int F1: allSums){
  52.         bool ok = true;
  53.         for(long long d: forbidden){
  54.             if(allSums.find(F1+d)==allSums.end()){ ok=false; break;}
  55.         }
  56.         if(!ok) continue;
  57.         // F1+D 범위 안에 다른 sum이 있으면 안됨
  58.         for(auto s: allSums){
  59.             long long diff = s-F1;
  60.             if(diff<0 || diff>maxD) continue;
  61.             if(forbidden.find(diff)==forbidden.end()){ ok=false; break;}
  62.         }
  63.         if(ok) ans++;
  64.     }
  65.  
  66.     cout << ans << "\n";
  67. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2 3 2
1 3
0 2
stdout
copy 
0
https://ideone.com/ANm1Bm
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!