結果
問題 | No.1334 Multiply or Add |
ユーザー |
![]() |
提出日時 | 2020-11-03 04:12:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 1,783 bytes |
コンパイル時間 | 2,111 ms |
コンパイル使用メモリ | 176,764 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 15:19:10 |
合計ジャッジ時間 | 7,901 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
#include<bits/stdc++.h>using std::cin;using std::cout;using std::endl;using std::vector;using ll=long long;const int mod=1e9+7;int main(){int N; cin>>N;vector<int> A(N);for(int i=0;i<N;i++) cin>>A[i];{vector<int> B=A;sort(B.begin(),B.end());if(B[N-1]==1){cout<<N<<endl;return 0;}}ll ans=1;for(int i=0;i<N;i++){ans*=A[i];if(ans>=2*N) break;}if(ans>=2*N){ans=1;for(int i=0;i<N;i++){ans*=A[i];ans%=mod;}for(int i=0;i<N;i++){if(A[i]>1) break;ans++;}for(int i=N-1;i>=0;i--){if(A[i]>1) break;ans++;}ans%=mod;cout<<ans<<endl;return 0;}ans=0;for(int i=N-1;i>=0;i--){if(A[i]>1) break;ans++;A.pop_back();}reverse(A.begin(),A.end());for(int i=A.size()-1;i>=0;i--){if(A[i]>1) break;ans++;A.pop_back();}vector<int> comp(1,A[0]);for(int i=1;i<A.size();i++){if(A[i]>1){if(A[i-1]>1) comp[comp.size()-1]*=A[i];else comp.push_back(A[i]);}else{if(A[i-1]>1) comp.push_back(1);else comp[comp.size()-1]++;}}int M=comp.size();ll max=0;for(int i=0;i<(1<<M/2);i++){ll sum=0,now=comp[0];for(int j=1;j<M;j+=2){if(i&(1<<(j/2))){now*=comp[j+1];}else{sum+=now+comp[j];now=comp[j+1];}}sum+=now;max=std::max(max,sum);}ans+=max;cout<<ans<<endl;}