Submission #1086527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086527		juicy	Homework (CEOI22_homework)	C++17	100 / 100	64 ms	81256 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  string s; cin >> s;
  int n = s.size();
  vector<int> a(n), b(n);
  vector<array<int, 2>> st;
  int c = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'm') {
      st.push_back({i, 0});      
      i += 3;
    } else if (s[i] == '?') {
      while (st.size() && st.back()[1]) {
        int j = st.back()[0];
        if (s[j + 1] == 'a') {
          a[i] += a[j] + 1;
          b[i] = min(b[i], b[j]);
        } else {
          a[i] = min(a[i], a[j]);
          b[i] += b[j] + 1;
        } 
        st.pop_back();
      }
      ++c;
      if (!st.size()) {
        cout << c - a[i] - b[i];
        break;
      }
      int l = st.back()[0];
      tie(a[l], b[l]) = tie(a[i], b[i]);
      st.back()[1] = 1;
    }
  }
  return 0;
}

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