fork(1) download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 1e6 + 5;
  7. const int inf = 1e8;
  8. string s;
  9. int dp[N][4], curID = 0, curPos = 0, ans = 1;
  10. inline int calc(int x, int y) {
  11.     if (x == -inf || y == -inf) return -inf;
  12.     return x + y;
  13. }
  14. inline void ckmax(int &u, int v) {
  15.     if (u < v) u = v;
  16. }
  17. int DP() {
  18.     int id = curID++;
  19.     // cerr << curPos << " " << id << '\n';
  20.     if (s[curPos] == 'S') {
  21.         dp[id][0] = dp[id][1] = dp[id][2] = dp[id][3] = -inf;
  22.         curPos++; int l = DP(); 
  23.         curPos++; int r = DP();     
  24.         // cerr << id << ": " << l << " " << r << '\n';
  25.  
  26.         ckmax(dp[id][0], calc(dp[l][0], dp[r][0]));
  27.         ckmax(dp[id][0], calc(dp[l][2], dp[r][1]) - 1);
  28.  
  29.         ckmax(dp[id][1], calc(dp[l][1], dp[r][0]));
  30.         ckmax(dp[id][1], calc(dp[l][3], dp[r][1]) - 1);
  31.  
  32.         ckmax(dp[id][2], calc(dp[l][0], dp[r][2]));
  33.         ckmax(dp[id][2], calc(dp[l][2], dp[r][3]) - 1);
  34.  
  35.         ckmax(dp[id][3], calc(dp[l][1], dp[r][2]));
  36.         ckmax(dp[id][3], calc(dp[l][3], dp[r][3]) - 1);
  37.     }
  38.     else if (s[curPos] == 'P') {
  39.         dp[id][0] = dp[id][1] = dp[id][2] = dp[id][3] = -inf;
  40.         curPos++; int l = DP();
  41.         curPos++; int r = DP();
  42.         // cerr << id << ": " << l << " " << r << '\n';
  43.  
  44.         ckmax(dp[id][0], calc(dp[l][0], dp[r][0]));
  45.         ckmax(dp[id][1], calc(dp[l][1], dp[r][1]) - 1);
  46.         ckmax(dp[id][2], calc(dp[l][2], dp[r][2]) - 1);
  47.         ckmax(dp[id][3], calc(dp[l][3], dp[r][3]) - 2);
  48.     }
  49.     else {
  50.         dp[id][0] = 0;
  51.         dp[id][1] = 1;
  52.         dp[id][2] = 1;
  53.         dp[id][3] = -inf;
  54.     }
  55.     // cerr << " -> " << id << ": " << dp[id][0] << " " << dp[id][1] << " " << dp[id][2] << " " << dp[id][3] << "\n";
  56.     return id;
  57. }
  58. signed main() {
  59.     cin.tie(NULL)->sync_with_stdio(false);
  60.     if(ifstream("INDEP.inp")) {
  61.         freopen("INDEP.inp", "r", stdin);
  62.         freopen("INDEP.out", "w", stdout);
  63.     }
  64.     cin >> s;
  65.     int id = DP();
  66.     for (int i = 0; i < 4; i++) ckmax(ans, dp[id][i]);
  67.     cout << ans;
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/UBl0YJ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!