oj.uz

Submission #443551

# Submission time Handle Problem Language Result Execution time Memory
443551 2021-07-10T18:31:01 Z penguinhacker Kvalitetni (COCI16_kvalitetni) C++14
120 / 120
 9 ms 1240 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, z[50], si;
string s;

double solve() {
	assert(s[si++]=='(');
	if (s[si]=='?') {
		si+=2;
		return z[0];
	}
	vector<double> v;
	char op='-';
	while(1) {
		v.push_back(solve());
		char cur=s[si++];
		if (cur==')')
			break;
		op=cur;
	}
	assert(v.size()>=2&&op=='+'||op=='*');
	if (op=='+')
		return min((double)z[v.size()-1], accumulate(v.begin(), v.end(), 0.0));
	double lb=0, rb=z[v.size()-1];
	for (int k=0; k<40; ++k) {
		double mid=(lb+rb)/2;
		double sum=0;
		for (double i : v)
			sum+=min(i, mid);
		if (sum<=z[v.size()-1])
			lb=mid;
		else
			rb=mid;
	}
	double p=1;
	for (double i : v)
		p*=min(i, lb);
	return p;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> z[i];
	cin >> s;
	cout << fixed << setprecision(3) << solve();
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from kvalitetni.cpp:1:
kvalitetni.cpp: In function 'double solve()':
kvalitetni.cpp:25:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |  assert(v.size()>=2&&op=='+'||op=='*');
      |         ~~~~~~~~~~~^~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 5 ms 844 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 576 KB Output is correct
2 Correct 6 ms 864 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 9 ms 1240 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 6 ms 1240 KB Output is correct