Submission #788633

#	Time	Username	Problem	Language	Result	Execution time	Memory
788633		WLZ	Homework (CEOI22_homework)	C++17	100 / 100	157 ms	123796 KiB

Main

#include <bits/stdc++.h>
using namespace std;

string s;
vector<int> comma;

int solve(int l, int r, bool greater) {
  if (s[l] == '?') return 1;
  int i = comma[l + 3];
  int x = solve(l + 4, i - 1, greater), y = solve(i + 1, r - 1, greater);
  if (greater) {
    if (s[l + 1] == 'a') return min(x, y);
    else return x + y;
  } else {
    if (s[l + 1] == 'a') return x + y;
    else return min(x, y);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  int n = (int) s.length();
  stack<int> st;
  comma.assign(n, -1);
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') st.push(i);
    if (s[i] == ')') st.pop();
    if (s[i] == ',') comma[st.top()] = i;
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) if (s[i] == '?') cnt++;
  int mx = cnt - solve(0, n - 1, true) + 1, mn = solve(0, n - 1, false);
  cout << mx - mn + 1 << '\n';
  return 0;
}

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