Submission #883682

#	Time	Username	Problem	Language	Result	Execution time	Memory
883682		vjudge1	Kvalitetni (COCI16_kvalitetni)	C++17	120 / 120	7 ms	7012 KiB

kvalitetni

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=1e3+100;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

double a[51];
vector<int>types;
vector<vector<int>>v;
double dfs(int node){
    if(!types[node]){
        if(v[node].size())return dfs(v[node][0]);
        return a[1];
    }
    else if(types[node]==1){
        double sum=0;
        for(int j:v[node]){
            sum+=dfs(j);
        }
        return min(sum,a[v[node].size()]);
    }
    else{
        vector<double>vals;
        for(int j:v[node]){
            vals.pb(dfs(j));
        }
        sort(vals.begin(),vals.end());
        double ans=1,can=a[v[node].size()];
        for(int i=0;i<vals.size();i++){
            if(vals[i]>=can/(vals.size()-i)){
                ans*=can/(vals.size()-i);
                can-=can/(vals.size()-i);
            }
            else{
                ans*=vals[i];
                can-=vals[i];
            }
        }
        return ans;
    }
}
inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    string s;
    cin>>s;
    stack<int>curhave;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            if(curhave.size())v[curhave.top()].pb(v.size());
            types.pb(0);
            curhave.push(v.size());
            v.pb(vector<int>());
        }else if(s[i]=='+'){
            types[curhave.top()]=1;
        }else if(s[i]=='*'){
            types[curhave.top()]=2;
        }else if(s[i]==')'){
            curhave.pop();
        }
    }
    cout<<dfs(0)<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("grass.in","r",stdin);
    //freopen("grass.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

kvalitetni.cpp: In function 'double dfs(long long int)':
kvalitetni.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0;i<vals.size();i++){
      |                     ~^~~~~~~~~~~~
kvalitetni.cpp: In function 'void solve()':
kvalitetni.cpp:61:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

• 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