結果
問題 |
No.983 Convolution
|
ユーザー |
![]() |
提出日時 | 2020-02-12 19:03:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,231 bytes |
コンパイル時間 | 1,899 ms |
コンパイル使用メモリ | 172,248 KB |
実行使用メモリ | 27,992 KB |
最終ジャッジ日時 | 2024-10-04 03:36:56 |
合計ジャッジ時間 | 8,366 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 WA * 3 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=__int128; ll mygcd(ll a,ll b){ return b==0 ? a : mygcd(b,a%b); } const int LOG_N=18; const int MAX_N=1<<LOG_N; ll B[MAX_N]; ll cross(ll a,ll b){ return min(a,b)==-1LL ? -1LL : a*b; } void add(ll& lhs,ll v){ if(min(lhs,v)==-1) lhs=-1; else lhs+=v; } void solve(int step,vector<ll> A,int mask){ if(A.size()==1){ add(B[mask],cross(A[0],A[0])); return; } vector<ll> odd(A.size()/2); for(int i=1;i<A.size();i+=2) odd[i/2]=A[i]; solve(step+1,odd,mask+(1<<step)); vector<ll> even(A.size()/2); for(int i=0;i<A.size();i++) add(even[i/2],A[i]); solve(step+1,even,mask); } string to_str(ll v){ string res; while(v){ res+=('0'+v%10); v/=10; } reverse(res.begin(),res.end()); return res; } int main(){ int n; cin>>n; vector<ll> A(MAX_N); for(int i=0;i<n;i++){ int tmp; cin>>tmp; A[i]=tmp; } solve(0,A,0); for(int i=0;i<MAX_N;i++){ if(B[i]==-1) B[i]=0; } ll ans=0; for(int i=0;i<MAX_N;i++){ ans=mygcd(ans,B[i]); } if(ans==0) cout<<-1<<endl; else cout<<to_str(ans)<<endl; return 0; }