結果
問題 | No.1929 Exponential Sequence |
ユーザー |
![]() |
提出日時 | 2022-05-06 23:02:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 1,395 bytes |
コンパイル時間 | 2,545 ms |
コンパイル使用メモリ | 200,260 KB |
最終ジャッジ日時 | 2025-01-29 04:04:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int u; void dfs(int *a, int *b, int *c, int d, int s, int r) { int t = 1; for (int i = 1; i < c[d]; i++) { t *= a[d]; if (r + t > s) break; if (d == 0) { b[u++] = r + t; } else { dfs(a, b, c, d - 1, s, r + t); } } } int main() { int n, s; cin >> n >> s; int a[8], c[8]; for (int i = 0; i < n; i++) { cin >> a[i]; ll t = 1; for (int j = 1;; j++) { t *= a[i]; if (t > s) { c[i] = j; break; } } } int m[2]; m[0] = min(n, 4); m[1] = n - m[0]; vector<int> b[2]; for (int h = 0; h < 2; h++) { int t = 1; for (int i = 0; i < m[h]; i++) { t *= c[i + h * m[0]]; } b[h].resize(t, s + 1); if (m[h] == 0) { b[h][0] = 0; } else { u = 0; dfs(a + h * m[0], &b[h][0], c + h * m[0], m[h] - 1, s, 0); } sort(b[h].begin(), b[h].end()); } ll r = 0; int k = b[0].size(), j = b[1].size() - 1; for (int i = 0; i < k; i++) { while (j >= 0 && b[0][i] + b[1][j] > s) j--; r += j + 1; } //cout << b[0].size() << ' ' << b[1].size() << endl; cout << r << endl; return 0; }