結果
問題 |
No.1929 Exponential Sequence
|
ユーザー |
|
提出日時 | 2022-09-13 20:58:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 835 bytes |
コンパイル時間 | 932 ms |
コンパイル使用メモリ | 69,376 KB |
実行使用メモリ | 8,972 KB |
最終ジャッジ日時 | 2024-12-14 05:04:32 |
合計ジャッジ時間 | 2,311 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 8; int n, s, a[N]; int s1[1000005], l1; int s2[1000005], l2; void dfs1(int i, int sum) { if (i == n / 2) { s1[++l1] = sum; return; } int x = 1; while (1ll * x * a[i] + sum <= s) { x *= a[i]; dfs1(i + 1, sum + x); } } void dfs2(int i, int sum) { if (i == n) { s2[++l2] = sum; return; } int x = 1; while (1ll * x * a[i] + sum <= s) { x *= a[i]; dfs2(i + 1, sum + x); } } int main() { cin >> n >> s; for (int i = 0; i != n; i++) cin >> a[i]; dfs1(0, 0), dfs2(n / 2, 0); sort(s1 + 1, s1 + l1 + 1), sort(s2 + 1, s2 + l2 + 1); long long ans = 0; for (int i = 1, j = l2; i <= l1; i++) { while (s1[i] + s2[j] > s) j--; ans += j; } cout << ans << endl; }