제출 #148751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148751		OnePiece (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	25 ms	3456 KiB

hiccup

#include "hiccup.h"
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <climits>
#include <cstring>
#include <ctime>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define REP(i,t) for(int i=0; i<(t); i++)
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define FORL(i,s,t) for(L i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)
#define EPS 1e-11
#define EQ(a, b) (fabs((a) - (b)) <= EPS)
#define POS(a) ((a) >= EPS)
#define NEG(a) ((a) <= -EPS)
#define BG(a, b) ((a) - (b) >= EPS)
#define LS(a, b) ((b) - (a) >= EPS)
#define CLR(a, x) memset( a, x, sizeof( a ) )
#define PI (atan(1.0) * 4)
#define SQ(x) ((x) * (x))
#define DIST(x1, y1, x2, y2) (sqrt(SQ((x1) - (x2)) + SQ((y1) - (y2))))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define setmin(a, b) (a = min(a, b))
#define setmax(a, b) (a = max(a, b))
#define LOG2(x) (log(x) / log(2))
#define XX first.first
#define XY first.second
#define YX second.first
#define YY second.second

using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<double, double> Pd;
typedef pair<int, int> Pi;
typedef pair<LL, LL> Pl;

struct Val {
	bool c;
	int m;
};

int HicCup(std::string S) {
	int len = S.length();
	std::stack<Val> st;
	int ans = INT_MAX;
	for (int i = 0; i < len; ++i) {
		if (S[i] == 'H') {
			st.push({false, 0});
		} else if (S[i] == 'C') {
			int cur_ans = INT_MAX;
			int cnt = 0;
			int r = 0;
			while (!st.empty() && st.top().c) {
				if (st.top().m + r >= cur_ans) {
					cnt++;
					r = st.top().m + r - cur_ans;
				} else {
					int total = cur_ans * cnt + r + st.top().m;
					cur_ans = total / (cnt + 1);
					cnt++;
					r = total - cur_ans * cnt;
				}
				st.pop();
			}
			ans = min(ans, cur_ans);
			if (st.empty()) return -1;
			st.top().c = true;
		} else if (S[i] == '!') {
			if (st.empty()) return -1;
			if (!st.top().c) return -1;
			st.top().m++;
		} else {
			return -1;
		}
	}
	int cnt = 0;
	int r = 0;
	int cur_ans = INT_MAX;
	while (!st.empty()) {
		if (!st.top().c) return -1;
		if (st.top().m + r >= cur_ans) {
			cnt++;
			r = st.top().m + r - cur_ans;
		} else {
			int total = cur_ans * cnt + r + st.top().m;
			cur_ans = total / (cnt + 1);
			cnt++;
			r = total - cur_ans * cnt;
		}
		st.pop();
	}
	ans = min(ans, cur_ans);
	return ans;
}

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