| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 369924 | FatihSolak | Kvalitetni (COCI16_kvalitetni) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define N 1000005
#define K 55
using namespace std;
int arr[K];
int c[N];
string s;
long double calc(int l,int r){
if(l +2 == r){
return arr[1];
}
bool carp = 0;
l++;
if(c[l] != r && s[c[l]+1] == '*')carp = 1;
vector<long double> nums;
while(l < r){
nums.push_back(calc(l,c[l]));
l = c[l]+2;
}
sort(nums.begin(),nums.end());
if(carp){
long double ret = 1;
long double remain = arr[nums.size()];
for(int i=0;i<nums.size();i++){
long double now = min(nums[i],(remain)/(nums.size()-i));
ret *= now;
remain -= now;
}
return ret;
}
else{
long double ret = 0;
for(auto u:nums)ret+=u;
return min(ret,1.0*arr[nums.size()]);
}
}
void solve(){
int k;
cin >> k;
for(int i=1;i<=k;i++){
cin >> arr[i];
}
cin >> s;
stack<int> st;
for(int i=0;i<s.length();i++){
if(s[i] == '('){
st.push(i);
}
if(s[i] == ')'){
c[st.top()] = i;
st.pop();
}
}
cout << fixed << setprecision(6) << calc(0,s.length()-1);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}