제출 #150847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150847		usa1+samsung2 (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	43 ms	5492 KiB

hiccup

#include "hiccup.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

bool pred(const vector<int>& v, const int& g) {
    int rem = 0;
    for(int i=0; i<(int)v.size(); i++){
        if(v[i] >= g) {
            rem += v[i]-g;
        } else if ((v[i]+rem) >= g) {
            rem += v[i]+rem-g;
        } else return false;
    }
    return true;
}

int HicCup(std::string S) {
	int N = S.size();
        int x = 0;
        int lo = 0;
        int hi = 0;
        int ans = 0;
        vector<int> v;
        if (N==0) return 0;
        if (S[0] != 'H') return -1;

        {
            char ex = S[0];
            stack<char> stk;
            stk.push('H');
            for(int i = 1 ; i < N;i++) {
                const char &s = S[i];
                if((s != 'H') && (s!='C') && (s!='!')){
                    return -1;
                }
                switch(ex) {
                    case 'H':
                        if(s=='!') {
                            return -1;
                        }
                        break;
                    case 'C':
                        break;
                    case '!':
                        break;
                    default:
                        return -1;
                        break;
                }
                if(s!='!') ex = s;
                if(s=='H') stk.push('H');
                else if(s=='C') {
                    if(!stk.empty()) stk.pop();
                    else return -1;
                }
            }
            if(ex=='H' || !stk.empty()) return -1;
        }
        for(int i=N-1;i>=0;i--) {
            if(S[i] == '!') x++;
            else if(S[i] == 'C') {
                v.push_back(x);
                hi = max(hi, x);
                x=0;
            }
        }
        {
            int mid;
            while(lo<=hi){
                mid = (lo+hi)/2;
                if(pred(v, mid)) {
                    ans = max(ans, mid);
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return ans;
}

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