Submission #640876

#	Time	Username	Problem	Language	Result	Execution time	Memory
640876		Alexandruabcde	Homework (CEOI22_homework)	C++14	100 / 100	229 ms	92012 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct Node {
   int st, dr;

   int sz;

   Node () {
      st = 1, dr = 0;

      sz = 0;
   }
};

string S;
int pos = 0;

Node Join (Node a, Node b, bool op) {
   Node ans;
   ans.sz = a.sz + b.sz;

   if (op == false) {
      ans.st = min(a.st, b.st);
      ans.dr = a.dr + b.dr - 1;
   }
   else {
      ans.st = a.st + b.st;
      ans.dr = max(a.dr + b.sz, a.sz + b.dr);
   }

   ans.sz = a.sz + b.sz;

   return ans;
}

Node Eval () {
   if (S[pos] == '?') {
      Node ans;

      ans.st = 1, ans.dr = 1, ans.sz = 1;

      return ans;
   }

   bool op = 0;
   if (S[pos] == 'm' && S[pos+1] == 'a' && S[pos+2] == 'x') op = 1;

   Node a, b;

   pos += 4;

   a = Eval();
   pos += 2;
   b = Eval();
   ++ pos;

   return Join(a, b, op);
}

int main () {
   cin >> S;

   Node ans = Eval();

   cout << ans.dr - ans.st + 1 << '\n';
   return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34