Submission #149007

#	Time	Username	Problem	Language	Result	Execution time	Memory
149007		본인 방금 올솔하는 상상함 (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	49 ms	14848 KiB

hiccup

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

using namespace std;
typedef pair<int,int> pi;

int cnt[N];
int ch[N];
int nxt[N];
int asdf[N];

int HicCup(std::string S) {
	int n = S.size();
	stack<pi> st;
	stack<pi> st2;
	int lv=0;
	int last=0;
	for(int i=0;i<n;i++){
		if(S[i]=='H'){
			lv++;
			st.push(pi(i, lv));
			st2.push(pi(i, lv));
		}
		else if(S[i]=='C'){
			if(st.empty()) return -1;
			pi t=st.top();
			st.pop();
			while(!st2.empty()&&(st2.top().second>lv||st2.top()==t)){
				st2.pop();
			}
			if(!st2.empty()) {
				nxt[st2.top().first]=t.first+1;
			}
			st2.push(t);
			lv--;
		}
		else{
			if(st2.empty()||lv==st2.top().second) return -1;
			cnt[st2.top().first]++;
		}
	}
	if(!st.empty()) return -1;
	int sum=0;
	int c=0;
	int ans=INT_MAX;
	for(int i=0;i<n;i++){
		if(ch[i]) continue;
		if(S[i]!='H') continue;
		else{
			sum=0;
			c=0;
			for(int j=i+1;j;j=nxt[j-1]){
				ch[j-1]=1;
				sum+=cnt[j-1];
				c++;
			}
			ans=min(ans, sum/c);
		}
	}
	return ans;
}

Compilation message (stderr)

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:18:6: warning: unused variable 'last' [-Wunused-variable]
  int last=0;
      ^~~~

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