fork(2) download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define sz(v) (int)v.size()
  4. #define pb push_back
  5.  
  6. using namespace std;
  7.  
  8. const int MXN = (int)1e6 + 10;
  9.  
  10. int n, k;
  11. string s;
  12. int pos_r[MXN];
  13. vector <int> tmp;
  14. double a[MXN];
  15.  
  16. double f(int l, int r){
  17.   if(l + 2 == r){
  18.     return a[1];
  19.   }
  20.   if(pos_r[l + 1] == r - 1){
  21.     return min(f(l + 1, r - 1), a[1]);
  22.   }
  23.   bool sign = (s[pos_r[l + 1] + 1] == '*');//false +, true *
  24.   vector <double> temp;
  25.   temp.clear();
  26.   //cerr << l << " " << r << "\n";
  27.   for(int i = l + 1; i < r; ){
  28.     temp.pb(f(i, pos_r[i]));
  29.     i = pos_r[i] + 2;
  30.   }
  31.   if(sign){
  32.     sort(temp.begin(), temp.end());
  33.     double cur_sum = a[sz(temp)];
  34.     double tmp1;
  35.     double ret = 1.0;
  36.     for(int i = 0; i < sz(temp); ++i){
  37.       tmp1 = min(temp[i], cur_sum / (1.0 * (sz(temp) - i)));
  38.       ret *= tmp1;
  39.       cur_sum -= tmp1;
  40.     }
  41.     return ret;
  42.   }
  43.   else {
  44.     double sum = 0;
  45.     for(int i = 0; i < sz(temp); ++i){
  46.       sum += temp[i];
  47.     }
  48.     return min(sum, a[sz(temp)]);
  49.   }
  50. }
  51.  
  52. int main(){
  53.   ios_base::sync_with_stdio(0);
  54.   cin >> k;
  55.   for(int i = 1; i <= k; ++i){
  56.     cin >> a[i];
  57.   }
  58.   cin >> s;
  59.   n = sz(s);
  60.   for(int i = 0; i < n; ++i){
  61.     if(s[i] == '('){
  62.       tmp.pb(i);
  63.     }
  64.     if(s[i] == ')'){
  65.       pos_r[tmp.back()] = i;
  66.       tmp.pop_back();
  67.     }
  68.   }
  69.   cout << fixed << setprecision(9) << f(0, n - 1);
  70.   return 0;
  71. }
  72.  
Success #stdin #stdout 0s 15184KB
comments (?)
stdin 
3
2 5 3
(((?)+(?))*(?))
stdout 
6.000000000
https://ideone.com/k9CUPD
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!