제출 #150564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150564		HSNU (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	62 ms	4352 KiB

hiccup

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

using namespace std;

bool chk(string s)
{
    if (s[0] == '!')
        return false;
    for (int i = 1; i < (int)s.size(); i++)
        if (s[i] == '!' && s[i - 1] == 'H')
            return false;

    stack<char> stk;
    for (int i = 0; i < (int)s.size(); i++)
        if (s[i] == '!')
            continue;
        else if (stk.empty())
            stk.push(s[i]);
        else if (stk.top() == 'H' && s[i] == 'C')
            stk.pop();
        else
            stk.push(s[i]);

    return stk.empty();
}

int HicCup(string s)
{
	long long N = s.size();

	if (!chk(s))
        return -1;

    long long ans = N;

    stack<long long> stk;
    for (int i = 0; i < (int)s.size(); i++)
    {
        if (s[i] == 'H')
            stk.push(-1);
        else
        {
            long long ttl = 0, cnt = 0;
            vector<long long> quu;
            while (stk.top() != -1)
                quu.push_back(stk.top()), ttl += stk.top(), cnt++, stk.pop();
            stk.pop();

            if (cnt)
            {
                long long avg = ttl / cnt;
                for (int i = 0; i < cnt - 1; i++)
                    if (quu[i] < avg)
                        ans = min(ans, quu[i]);
                    else
                        quu[i + 1] += quu[i] - avg, quu[i] = avg;
                ans = min(ans, min(quu[cnt - 1], avg));
            }

            i++;
            cnt = 0;
            while (s[i] == '!' && i < (int)s.size())
                cnt++, i++;
            i--;
            stk.push(cnt);
        }
    }

    long long ttl = 0, cnt = 0;
    vector<long long> quu;
    while (!stk.empty())
        quu.push_back(stk.top()), ttl += stk.top(), cnt++, stk.pop();

    if (cnt)
    {
        long long avg = ttl / cnt;
        for (int i = 0; i < cnt - 1; i++)
            if (quu[i] < avg)
                ans = min(ans, quu[i]);
            else
                quu[i + 1] += quu[i] - avg, quu[i] = avg;
        ans = min(ans, min(quu[cnt - 1], avg));
    }

	return (int)ans;
}

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