結果
問題 | No.1929 Exponential Sequence |
ユーザー |
![]() |
提出日時 | 2022-05-06 22:05:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 1,372 bytes |
コンパイル時間 | 1,194 ms |
コンパイル使用メモリ | 80,028 KB |
最終ジャッジ日時 | 2025-01-29 03:28:19 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; vector<ll> v1,v2; void dfs1(vector<ll> &v,ll sum,ll mx,int pos){ if(pos==v.size()){ if(sum<=mx) v1.push_back(sum); }else{ ll x = v[pos]; for(int i=0;i<40;i++){ if(sum + x<=mx) dfs1(v,sum + x,mx,pos + 1); else break; x *= v[pos]; } } } void dfs2(vector<ll> &v,ll sum,ll mx, int pos){ if(pos==v.size()){ if(sum<=mx) v2.push_back(sum); }else{ ll x = v[pos]; for(int i=0;i<40;i++){ if(sum + x<=mx) dfs2(v,sum + x,mx,pos + 1); else break; x *= v[pos]; } } } int a[10]; int main(){ int i,n,s; cin >> n >> s; for(i=0;i<n;i++) cin >> a[i]; vector<ll> v; for(i=0;i<min(n,4);i++) v.push_back(a[i]); dfs1(v,0,s,0); if(n>4){ v.clear(); for(i=4;i<n;i++) v.push_back(a[i]); dfs2(v,0,s,0); } sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); /*for(ll x:v2) cout << x << " "; cout << endl; cout << v1.size() << endl;*/ ll ans = 0; if(n<=4){ ans = v1.size(); }else{ for(ll x:v1){ ll num = upper_bound(v2.begin(),v2.end(),s - x) - v2.begin(); ans += num; } } cout << ans << endl; }