oj.uz

Submission #883682

# Submission time Handle Problem Language Result Execution time Memory
883682 2023-12-05T17:16:42 Z vjudge1 Kvalitetni (COCI16_kvalitetni) C++17
120 / 120
 7 ms 7012 KB 
#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

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

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 3224 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1688 KB Output is correct
2 Correct 6 ms 3340 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2968 KB Output is correct
2 Correct 7 ms 7012 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2068 KB Output is correct
2 Correct 6 ms 6540 KB Output is correct