結果
問題 |
No.1929 Exponential Sequence
|
ユーザー |
![]() |
提出日時 | 2022-05-08 21:30:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 606 ms |
コンパイル使用メモリ | 57,684 KB |
実行使用メモリ | 8,020 KB |
最終ジャッジ日時 | 2024-09-14 03:55:03 |
合計ジャッジ時間 | 2,228 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
/* -*- coding: utf-8 -*- * * 1929.cc: No.1929 Exponential Sequence - yukicoder */ #include<cstdio> #include<map> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 8; const int MAX_M = 30 * 30 * 30 * 30; /* typedef */ typedef long long ll; typedef map<int,int> mii; /* global variables */ int as[MAX_N], bs[MAX_M], ss[MAX_M + 1]; /* subroutines */ void rec(int k, int n, int s, int sum, mii &scs) { if (k >= n) { scs[sum]++; return; } for (ll ea = as[k]; sum + ea <= s; ea *= as[k]) rec(k + 1, n, s, sum + ea, scs); } /* main */ int main() { int n, s; scanf("%d%d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", as + i); int h = n / 2; mii scs0, scs1; if (h > 0) rec(0, h, s, 0, scs0); if (h < n) rec(h, n, s, 0, scs1); if (h == 0) { printf("%d\n", (int)scs1.size()); return 0; } int m = 0; for (auto sc: scs1) { bs[m] = sc.first; ss[m + 1] = ss[m] + sc.second; m++; } ll sum = 0; for (auto sc: scs0) { int si = sc.first, ci = sc.second; int k = upper_bound(bs, bs + m, s - si) - bs; sum += (ll)ci * ss[k]; } printf("%lld\n", sum); return 0; }