Submission #151211

#	Time	Username	Problem	Language	Result	Execution time	Memory
151211		rdd6584	HicCup (FXCUP4_hiccup)	C++17	100 / 100	30 ms	8824 KiB

hiccup

#include "hiccup.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

vector<int> v;
int hc[1000001];
string ss;
int ans = 1e9;

void dnc(int l, int r) {
	int cnt = 0, nf = 0, cc = 0;
	for (int i = r; i >= l; i--) {
		if (ss[i] == '!') {
			cnt++;
			nf = 1;
		}
		else {
			dnc(hc[i] + 1, i - 1);
			i = hc[i];
			cc++;
			ans = min(ans, cnt / cc);
			nf = 0;
		}
	}

	if (nf) ans = -1;
}

int HicCup(std::string s) {
	int n = s.size();
	ss = s;
	
	for (int i = 0; i < n; i++) {
		if (s[i] == 'H')
			v.push_back(i);
		else if (s[i] == 'C') {
			if (v.empty()) return -1;
			hc[i] = v.back();
			v.pop_back();
		}
	}

	if (!v.empty()) return -1;

	dnc(0, n - 1);
	// 가장 외곽 괄호쌍에서만 느낌표를 받을 수 있다.
	// C가 없는 것에 대한 예외처리 필요.
	// MIN..
	// 안쪽에 대해서만.
	// 
	// 그 괄호로 둘러쌓여져 있는 부분에서.
	// 

	return ans;
}

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