結果
問題 | No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん |
ユーザー | logx |
提出日時 | 2021-06-06 02:52:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 415 ms / 2,000 ms |
コード長 | 2,870 bytes |
コンパイル時間 | 2,199 ms |
コンパイル使用メモリ | 204,024 KB |
最終ジャッジ日時 | 2025-01-22 03:47:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#ifdef LOGX #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; //#include <atcoder/all> //using namespace atcoder; /*---------macro---------*/ #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = s; i < (int)(n); i++) #define unless(x) if(!(x)) #define until(x) while(!(x)) #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() #define mybit(i,j) (((i)>>(j))&1) /*---------type/const---------*/ const int big=1000000007; //const int big=998244353; const double EPS=1e-8; //適宜変える typedef long long ll; typedef unsigned long long ull; typedef std::string::const_iterator state; //構文解析 const int dx[4]={1,0,-1,0}; const int dy[4]={0,1,0,-1}; const char newl='\n'; struct{ constexpr operator int(){return -int(1e9)-10;} constexpr operator ll(){return -ll(1e18)-10;} }neginf; struct{ constexpr operator int(){return int(1e9)+10;} constexpr operator ll(){return ll(1e18)+10;} constexpr auto operator -(){return neginf;} }inf; /*---------debug---------*/ #ifdef LOGX #include <template/debug.hpp> #else #define dbg(...) ; #define dbgnewl ; #define prt(x) ; #define _prt(x) ; #endif /*---------function---------*/ template<typename T> T max(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;} template<typename T> T min(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;} template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;} template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;} bool valid(int i,int j,int h,int w){return (i>=0 && j>=0 && i<h && j<w);} template<class T,class U>T expm(T x,U y,const ll mod=big){T res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;} template<class T,class U>T exp(T x,U y){T res=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}return res;} int main(){ //std::ios::sync_with_stdio(false); //std::cin.tie(nullptr); std::cout.precision(10); /*------------------------------------*/ int n; cin >> n; string s; cin >> s; vector al(n+1,vector(n+1,false)); vector dp(n+1,vector(n+1,0)); auto f=[&](int i,int j,auto &f)->int{ if(al[i][j])return dp[i][j]; al[i][j]=true; if(i+3>j)return dp[i][j]=0; int p=-1,n=-1; for(int k=i;k<j;k++){ if(p==-1 && s[k]=='p')p=k; if(p!=-1 && s[k]=='n')n=k; } for(int k=i+1;k<j;k++){ chmax(dp[i][j],f(i,k,f)+f(k,j,f)); if(s[k]=='o' && p<k && k<n){ chmax(dp[i][j],f(p+1,k,f)+f(k+1,n,f)+1); } } return dp[i][j]; }; int ans=1; for(int i=0;i<n;i++){ if(f(0,i,f) && f(i,n,f))chmax(ans,f(0,i,f)+f(i,n,f)); } cout << ans-2 << newl; }