結果
問題 |
No.1929 Exponential Sequence
|
ユーザー |
|
提出日時 | 2022-05-07 02:38:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 942 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 7,764 KB |
最終ジャッジ日時 | 2024-09-14 03:54:53 |
合計ジャッジ時間 | 2,476 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
コンパイルメッセージ
main.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 37 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; int N,S; vector<int>A; vector<int>ret; void dfs(int id,int now) { if(id==A.size())ret.push_back(now); else { long t=A[id]; while(now+t<=S) { dfs(id+1,now+t); t*=A[id]; } } } vector<pair<int,long> >f(vector<int>A_) { A=A_; dfs(0,0); vector<pair<int,long> >cnt; sort(ret.begin(),ret.end()); for(int i=0;i<ret.size();) { int j=i; while(j<ret.size()&&ret[i]==ret[j])j++; cnt.push_back(make_pair(ret[i],j-i)); i=j; } ret.clear(); return cnt; } main() { cin>>N>>S; vector<int>Ai(N); for(int i=0;i<N;i++)cin>>Ai[i]; vector<pair<int,long> >L=f(vector<int>(Ai.begin(),Ai.begin()+N/2)); vector<pair<int,long> >R=f(vector<int>(Ai.begin()+N/2,Ai.end())); int r=0; long ans=0,sum=0; for(int l=L.size();l--;) { while(r<R.size()&&R[r].first+L[l].first<=S) { sum+=R[r++].second; } ans+=sum*L[l].second; } cout<<ans<<endl; }