제출 #148659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148659		본인 하지만 안 어림 ㅋㅋ (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	76 ms	4352 KiB

hiccup

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

#include "hiccup.h"

int HicCup(std::string s) {

	int n = s.size();

    int c = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'H')
            c++;
        else if(s[i] == 'C')
            c--;

        if(c < 0)
            return -1;
    }
    if(c != 0)
        return -1;

    s.insert(s.begin(), 'H');
    s.push_back('C');
    n = s.size();

    int l = 0;
    int r = n;
    while(l <= r)
    {
        int x = (l + r + 1) / 2;

        bool ok = 1;
        bool u = 0;
        int t = 0;
        stack<vector<int>> stk;
        stk.push(vector<int>());
        for(int i = 0; i < n; i++)
        {
            if(s[i] == 'H')
            {
                if(i != 0)
                {
                    stk.top().push_back(t);
                    t = 0;
                }

                stk.push(vector<int>());
                u = 0;
            }
            else if(s[i] == 'C')
            {
                stk.top().push_back(t);
                t = 0;

                assert(stk.top()[0] == 0);

                int sz = stk.top().size();
                int cnt = 0;
                for(int j = sz - 1; j >= 1; j--)
                {
                    cnt += stk.top()[j];
                    cnt -= x;
                    if(cnt < 0)
                    {
                        ok = 0;
                        break;
                    }
                }
                if(!ok)
                    break;

                stk.pop();

                u = 1;
            }
            else
            {
                if(!u)
                    return -1;
                t++;
            }
        }

        if(l == r)
        {
            assert(ok);
            return l;
        }

        if(ok)
            l = x;
        else
            r = x - 1;
    }
    assert(0);
}

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