oj.uz

Submission #532803

# Submission time Handle Problem Language Result Execution time Memory
532803 2022-03-04T00:43:22 Z colazcy Kvalitetni (COCI16_kvalitetni) C++17
120 / 120
 38 ms 50384 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47184 KB Output is correct
2 Correct 23 ms 47184 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47184 KB Output is correct
2 Correct 28 ms 47184 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47304 KB Output is correct
2 Correct 25 ms 47256 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47312 KB Output is correct
2 Correct 22 ms 47364 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47276 KB Output is correct
2 Correct 23 ms 47272 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47312 KB Output is correct
2 Correct 25 ms 47408 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47312 KB Output is correct
2 Correct 27 ms 48940 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48004 KB Output is correct
2 Correct 38 ms 49096 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48700 KB Output is correct
2 Correct 30 ms 50384 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48200 KB Output is correct
2 Correct 31 ms 50084 KB Output is correct