[典型90] 051 - Typical Shop（★5）

[Q] https://atcoder.jp/contests/typical90/tasks/typical90_ay

1. 半分全列挙
2. 累積和とっておく（沼った）

1. 半分全列挙
・箱
map<ll, ll> M1[44]; // M1[とる個数] = {総和, 何通り}
map<ll, ll> M2[44];

・初期条件は
M1[0][0]=1
M2[0][0]=1

0個 とる場合の 総和0 が 1通り

・入れ方は

Q. N=5 K=2 P=10
3 8 7 5 11

M1 = {3,8}
M2 = {7,5,11} をわける予定

・A[0]=3
M1に1個入れるので、
M1[1] = M1[0]のすべての組み合わせ + key(A[0])

M1[0]: 1個もとっていないすべての状態

・A[1]=8
M1 に 2個目を入れるので、
M1[2] = M1[1]のすべての組み合わせ + key(A[1])
M1[1] = M1[0]のすべての組み合わせ + key(A[1]) // もしA[0]を採用していなかった場合

・A[2]=7
M2にもする。
...

2. 累積和
N=40 K=20 で適当な値を考察すると
M1[20] = 100000通りくらいになる。
M1[20] * M2[20]の全通りを何も考えずにためすとTLEしちゃう。

M2を累積和とった。
たとえば
M[2][5] = { 10,1  20,3  30,5 } の3要素があったら // みやすいように{}をはずして適当に表記
M[2][5] = { 10,1  20,4  30,9 } に、要素数を累積しておく。
key=20以下の組み合わせが4通り。
key=30以下の組み合わせが9通り。

2. 累積和をとらなくても、vector()で入れておけば、lower_bound()で要素数のsize()がとれる。
mapじゃなくてvector()でやるのがベスト。

Ａに大きい値が入るからmapでやりたくなる。
実装

 
ll N, K, P;
ll A[44];
map<ll, ll> M1[44], M2[44];


int main(){
 cincout();
 
 cin >> N >> K >> P;
 rep(i, N) cin >> A[i];
 M1[0][0]=1;
 M2[0][0]=1;
 
 rep(i, N/2){
   ll a=A[i];
   for(ll j=i+1; j>0; --j){
     for(auto m: M1[j-1]){
       ll key=m.first;
       ll val=m.second;
       if(key+a>P) break;
       M1[j][key+a] += val;
     }
   }
 }

 for(ll i=N/2; i<N; ++i){
   ll a=A[i];
   for(ll j=i+1-N/2; j>0; --j){
     for(auto m: M2[j-1]){
       ll key=m.first;
       ll val=m.second;
       if(key+a>P) break;
       M2[j][key+a] += val;
     }
   }
 }
 
 /*
 M1[2]={1,3,5,7}
 M2[3]={1,3,5,7,9}
 
 {1,3}{1,5}{1,7}{1,9}
 これが100000*100000までに膨れうる
 
 M2だけ累積に
 */
 
 //M2の累積
 rep(i, K+1){
   ll t=0;
   for(auto m: M2[i]){
     t += m.second;
     M2[i][m.first] = t;
   }
 }
 
 ll ans=0;
 rep(i, K+1){
   if(M2[K-i].count(0)==0) M2[K-i][0]=0; // dummy begin()
   auto it = M2[K-i].upper_bound(P-M1[i].begin()->first);
   --it;
   for(auto m: M1[i]){
     while(it->first+m.first>P) --it;
     ans += it->second * m.second;
   }
 }
 
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/27745181