Submission #150351

#	Time	Username	Problem	Language	Result	Execution time	Memory
150351		Avengers (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	90 ms	38776 KiB

hiccup

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;

#include "hiccup.h"
vector<int> nums[1000006];
vector<int> v;
bool ok(int x, int id){
        v = nums[id];
        int N = v.size();
        int r = N - 1;

        fr(i, 0, N){
                if(v[i] < x){
                        for(int j = r; j > i; j --){
                                if(v[j] - x >= x - v[i]){
                                        v[i] = x;
                                        v[j] -= (x - v[i]);
                                        r = j;
                                        break;
                                }
                        }
                        if(v[i] < x) return false;
                }
        }

        return true;
}
int HicCup(std::string s) {
	int n = s.size();
	int cnt[n];
	int c =  0;
	for(int i = n - 1; i >= 0; i --){
                if(s[i] == '!') c ++;
                cnt[i] = c;
                if(s[i] == 'C') c = 0;
                else if(s[i] == 'H' && c > 0) return -1;
	}
	if(c > 0) return -1;

	stack <int> S;
	S.push(0);
	int ANS = n;
	fr(i, 0, n){
                if(s[i] == 'H') S.push(i + 1);
                else if(s[i] == 'C'){
                        if((int)(S.size()) == 1) return -1;
                        int id = S.top();
                        S.pop();
                        nums[(int)S.top()].pb(cnt[i]);
                        if(nums[id].empty()) continue;
                        int k = 0;
                        for(int b = (ANS+1)/ 2; b >= 1; b /= 2){
                                while(k + b <= ANS && ok(k + b, id)) k += b;
                        }
                        ANS = min(ANS, k);


                 }
        }
        if((int)S.size() > 1)return -1;
        if(!nums[0].empty()){
                int k = 0;
                for(int b = (ANS+1) / 2; b >= 1; b /= 2){
                        while(k + b <= ANS && ok(k + b, 0)) k += b;
                }
                ANS = min(ANS, k);
        }
        return ANS;
}/*
int main(){
         cout<< HicCup("HC!HC!!!!HC!!!!");
}*/

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