結果

問題 No.3210 Fixed Sign Sequense
ユーザー jiyujin816
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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]});
}
0