Submission #151412

#	Time	Username	Problem	Language	Result	Execution time	Memory
151412		AlexPop28	HicCup (FXCUP4_hiccup)	C++17	100 / 100	32 ms	8280 KiB

hiccup

#include <bits/stdc++.h>
#include "hiccup.h"

using namespace std;

const int INF = (int)1e9 + 5;

int Solve(int left, int right, const string &s, const vector<int> &lft) {
  if (left > right) {
    return INF;
  }
  if (s[left] == '!') {
    return -1;
  }
  int cnt_excl = 0, cnt_intervals = 0, ans = INF;
  for (int i = right; i >= left; --i) {
    if (s[i] == '!') {
      ++cnt_excl;
    } else {
      assert(s[i] == 'C');
      ++cnt_intervals;
      ans = min({ans, Solve(lft[i] + 1, i - 1, s, lft), cnt_excl / cnt_intervals});
      i = lft[i];
    }
  }
  return ans;
}

int HicCup(string s) {
  int n = s.length();
  vector<int> h_pos, lft(n);
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'H') {
      h_pos.emplace_back(i);
    } else if (s[i] == 'C') {
      if (h_pos.empty()) return -1;
      lft[i] = h_pos.back();
      h_pos.pop_back();
    }
  }
  if (!h_pos.empty()) return -1;
  return Solve(0, n - 1, s, lft);
}

• Subtask 1: 24 / 24
• Subtask 2: 76 / 76