Submission #149303

#	Time	Username	Problem	Language	Result	Execution time	Memory
149303		Cafe Maru (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	66 ms	3584 KiB

hiccup

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

constexpr int INF = 1111111;
int foo(vector<int>& s) {
    if (s.back() != 0) return -1;
    s.pop_back();
    int ret = INF;
    int ce = 0, cc = 0;
    for(int x : s) {
        ce += x;
        cc++;
        s.pop_back();
        ret = min(ret, ce/cc);
    }
    return ret;
}

int HicCup(std::string S) {
	int N = S.size();
    int ans = INF;
    vector<vector<int> > st;
    st.push_back(vector<int>(1,0));
    for(int i=N-1;i>=0;i--) {
        if (S[i] == 'H') {
            vector<int> c = move(st.back());
            st.pop_back();
            if (st.empty()) return -1;
            int t = foo(c);
            ans = min(ans, t);
        } else if (S[i] == 'C') {
            st.back().push_back(0);
            st.push_back(vector<int>(1,0));
        } else {
            st.back().back()++;
        }
    }
    vector<int> c = move(st.back());
    st.pop_back();
    if (!st.empty()) return -1;
    int t = foo(c);
    ans = min(ans, t);

    if(ans == INF) ans = 0;
	return ans;
}

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