結果
問題 |
No.1334 Multiply or Add
|
ユーザー |
![]() |
提出日時 | 2025-09-26 13:33:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 3,800 bytes |
コンパイル時間 | 7,202 ms |
コンパイル使用メモリ | 204,804 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-26 13:34:17 |
合計ジャッジ時間 | 7,399 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
// https://contest.ucup.ac/submission/1072091 // https://codeforces.com/contest/1461/submission/100952446 #include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=1000000007,MAX=200005; const ll INF=1<<30; ll A[MAX]; string solve(int l,int r){ int L=l,R=r; while(L<r&&A[L]==1) L++; while(R>=l&&A[R-1]==1) R--; string res; if(L>=R){ for(int i=l;i<r;i++){ if(i>l) res+='+'; } return res; } for(int i=l;i<L;i++){ res+='+'; } ll kake=1; for(int i=L;i<R;i++){ kake*=A[i]; if(kake>3*(R-L)) break; } if(kake>3*(R-L)){ for(int i=L;i<R;i++){ if(i>L) res+='*'; } for(int i=R;i<r;i++){ res+='+'; } return res; } vector<int> X; for(int i=L;i<R;i++){ if(A[i]>=2) X.push_back(i); } int M=si(X); if(M==1){ res.clear(); for(int i=l;i<r;i++){ if(i>l) res+='+'; } return res; } //cout<<"X"<<endl; pair<int,int> ma={-1,-1}; for(int bit=0;bit<(1<<(M-1));bit++){ int sum=0; int i=0; while(i<M-1){ if(!(bit&(1<<i))){ sum+=A[X[i]]; sum+=X[i+1]-X[i]-1; i++; if(i==M-1) sum+=A[X[M-1]]; }else{ int j=i; while(j<M-1&&(bit&(1<<j))) j++; int xx=1; for(int k=i;k<=j;k++){ xx*=A[X[k]]; } //cout<<i<<" "<<j<<" "<<xx<<endl; sum+=xx; if(j<M-1){ sum+=X[j+1]-X[j]-1; i=j; i++; if(i==M-1) sum+=A[X[M-1]]; }else{ break; } } } chmax(ma,mp(sum,bit)); //cout<<sum<<" "<<bit<<endl; } int bit=ma.se; for(int t=0;t<M-1;t++){ for(int i=X[t]+1;i<=X[t+1];i++){ if(bit&(1<<t)) res+='*'; else res+='+'; } } for(int i=R;i<r;i++){ res+='+'; } return res; } int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int Q=1; while(Q--){ int N;cin>>N; for(int i=0;i<N;i++){ cin>>A[i]; } string ans; int i=0; while(i<N){ int j=i; while(j<N&&A[j]==0) j++; for(int k=i;k<j;k++){ if(k) ans+='+'; } i=j; if(i>=N) break; while(j<N&&A[j]) j++; string S=solve(i,j); if(i) ans+='+'; ans+=S; i=j; //cout<<ans<<endl; } vector<ll> res={A[0]}; for(int i=0;i<N-1;i++){ if(ans[i]=='+'){ res.push_back(A[i+1]); }else{ res.back()*=A[i+1]; res.back()%=mod; } } ll sum=0; for(ll a:res){ sum+=a; sum%=mod; } cout<<sum<<"\n"; } }