結果
問題 |
No.3210 Fixed Sign Sequense
|
ユーザー |
|
提出日時 | 2025-07-25 21:30:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 3,031 bytes |
コンパイル時間 | 5,303 ms |
コンパイル使用メモリ | 335,288 KB |
実行使用メモリ | 21,240 KB |
最終ジャッジ日時 | 2025-07-25 21:30:45 |
合計ジャッジ時間 | 7,383 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> /*多倍長整数 #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; // 任意長整数型 using Bint = mp::cpp_int; //仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする) using Real = mp::number<mp::cpp_dec_float<1024>>; */ using namespace std; using namespace atcoder; using ll=long long; using ull=unsigned long long; using ld=long double; using mint=modint998244353; using mint2=modint1000000007; //任意modint using mint3=static_modint<1000000000>; using P=pair<ll,ll>; const ll INF=1e17; const vector<ll> dx={0,0,1,-1,1,1,-1,-1}; const vector<ll> dy={1,-1,0,0,1,-1,-1,1}; const vector<char> dirs={'>','<','v','^'}; #define rep(i,N) for(ll i=0;i<N;i++) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() template <typename T1,typename T2> ostream& operator<<(ostream &os,pair<T1,T2> &pai){ return os<<"("<<pai.first<<","<<pai.second<<") "; } template<typename T> ostream& operator<<(ostream &os,vector<T> vec){ for(auto val:vec){ os<<val<<" "; } return os<<"\n"; } template<typename T> istream& operator>>(istream &is,vector<T> &vec){ for(int i=0;i<(int)vec.size();i++){ is>>vec[i]; } return is; } template<typename T,typename T2> istream& operator>>(istream &is,pair<T,T2> &pai){ is>>pai.first>>pai.second; return is; } void set_cout(){ cout<<fixed<<setprecision(15); } template <typename T> void print(const T &vec){ int i=0; for(auto val:vec){ cout<<i<<":"<<val<<","; i++; } cout<<'\n'; } template<typename T> void print2(const vector<vector<T>> &vec){ int i=0; for(auto v:vec){ cout<<i<<": "; for(auto a:v){ cout<<a<<" "; } i++; cout<<'\n'; } } template<class T> void chmin(T &a,T b){ if(a>b){ a=b; } return; } template<class T> void chmax(T &a,T b){ if(a<b){ a=b; } return; } struct ob3{ ll a,b,c; bool operator<(const ob3 &o) const{ return a<o.a; } bool operator>(const ob3 &o) const{ return a>o.a; } }; struct ob4{ ll a,b,c,d; friend auto operator<=>(const ob4&,const ob4&)=default; }; int main(){ cin.tie(0)->sync_with_stdio(0); int N; cin>>N; string S; cin>>S; vector<int> comp(N); rep(i,N){ if(S[i]=='+'){ comp[i]=2; }else if(S[i]=='0'){ comp[i]=1; }else{ comp[i]=0; } } vector<vector<int>> dp(N,vector<int>(3,0)); dp[0][comp[0]]=1; for(int i=1;i<N;i++){ rep(j,3){ dp[i][j]=dp[i-1][j]; } int max_val=0; for(int j=0;j<=comp[i];j++){ chmax(max_val,dp[i-1][j]); } if(comp[i]==1){ max_val=dp[i-1][0]; } dp[i][comp[i]]=max_val+1; } cout<<max({dp[N-1][0],dp[N-1][1],dp[N-1][2]}); }