Submission #532803

#	Time	Username	Problem	Language	Result	Execution time	Memory
532803		colazcy	Kvalitetni (COCI16_kvalitetni)	C++17	120 / 120	38 ms	50384 KiB

kvalitetni

#include <cstdio>
#include <cassert>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using type = double;
constexpr int maxn = 2e6 + 10;

char str[maxn];
std::vector<int> G[maxn];
int k,n,tot,lim[64],match[maxn],opt[maxn];
int build(const int l = 1,const int r = n){
	if(str[l] == '(' && match[l] == r)return build(l + 1,r - 1);
	if(l == r)return ++tot;
	assert(match[l] + 1 <= r);
	let c = str[match[l] + 1];
	let x = ++tot;
	opt[x] = c == '+' ? 1 : 2;
	for(int i = l;i <= r;i = match[i] + 2)
		G[x].push_back(build(i,match[i]));
	return x;
}
type solve(const int x){
	if(opt[x] == 0)return lim[1];	
	assert(2 <= G[x].size() && (int)G[x].size() <= k);
	if(opt[x] == 1){
		type res = 0;
		for(let v : G[x])
			res += solve(v);
		return std::min(res,(type)lim[G[x].size()]);
	}
	if(opt[x] == 2){
		std::vector<type> vec;
		for(let v : G[x])vec.push_back(solve(v));
		std::sort(vec.begin(),vec.end());
		int rem = G[x].size();
		type sum = lim[G[x].size()],res = 1.0;
		for(let v : vec){
			let t = std::min(v,sum / rem);
			res *= t;
			sum -= t;
			rem--;
		}
		return res;		
	}
	assert(false);
}
int main(){
	// std::freopen("kvalitetni.in","r",stdin);
	// std::freopen("kvalitetni.out","w",stdout);
	std::scanf("%d",&k);
	rep(i,1,k)std::scanf("%d",lim + i);
	std::scanf("%s",str + 1);
	n = std::strlen(str + 1);
	std::stack<int> stk;
	rep(i,1,n)
		if(str[i] == '(')stk.push(i);
		else if(str[i] == ')'){
			match[stk.top()] = i;
			match[i] = stk.top();
			stk.pop();
		}	
	// rep(i,1,n)debug("%d ",match[i]);
	// debug("\n");
	let rt = build(1,n);
	std::printf("%.9lf\n",solve(rt));
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

kvalitetni.cpp: In function 'int main()':
kvalitetni.cpp:58:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  std::scanf("%d",&k);
      |  ~~~~~~~~~~^~~~~~~~~
kvalitetni.cpp:59:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  rep(i,1,k)std::scanf("%d",lim + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
kvalitetni.cpp:60:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  std::scanf("%s",str + 1);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12