結果
問題 | No.2145 Segment +- |
ユーザー |
![]() |
提出日時 | 2022-12-02 23:17:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 2,229 ms |
コンパイル使用メモリ | 193,408 KB |
最終ジャッジ日時 | 2025-02-09 04:24:34 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define INF 1234567890 #define ll long long int N; string s; int dp[200010][30][2]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin >> N >> s; for(int i=0; i<200010; i++) for(int j=0; j<30; j++) for(int k=0; k<2; k++) dp[i][j][k] = -INF; // base case dp[0][0][0] = 0; // cal dp for(int i=0; i<N; i++) for(int j=0; j<30; j++) for(int k=0; k<2; k++) if (dp[i][j][k] >= 0) { if (s[i] == '?') { dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] + 1); } else if (s[i] == '+') { if (k) { dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] - 1); dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k] + 1); } else { dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] + 1); } } else if (s[i] == '-') { if (k) { dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] + 1); dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k] - 1); } else { dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k] - 1); if (j+1 < 30) dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][k] + 1); } } else assert(0); } // find res for(int j=0; j<30; j++) if (dp[N][j][0] >= 0 || dp[N][j][1] >= 0) { cout << j << "\n"; return 0; } assert(0); return 0; }