Submission #1163198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163198		faruk	Kvalitetni (COCI16_kvalitetni)	C++20	120 / 120	8 ms	2276 KiB

kvalitetni

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef long double ld;

int k;
string s;
vector<ld> arr;
vector<int> nextes;

ld dfs(int l, int r) {
    if (r - l == 2)
        return arr[0];

    stack<int> opens;
    vector<ld> maxis;
    char sign = '+';
    for (int i = l + 1; i < r; i++) {
        if (s[i] == '(')
        {
            int nxt = nextes[i];
            if (maxis.empty())
                sign = s[nxt + 1];
            maxis.push_back(dfs(i, nxt));
            i = nxt;
        }
    }
    if (sign == '+') {
        return min(arr[maxis.size() - 1], accumulate(all(maxis), (ld)0.0));
    }

    sort(all(maxis));
    ld max_sum = arr[maxis.size() - 1];
    ld prod = 1;

    ld sum_all = accumulate(all(maxis), ld(0));
    bool flag = false; ld val = -1;
    for (int i = 0; i < maxis.size(); i++) {
        ld left = maxis.size() - i;
        if (maxis[i] < max_sum / left and !flag) {
            prod *= maxis[i];
            sum_all -= maxis[i];
            max_sum -= maxis[i];
        } else if (!flag) {
            flag = true;
            val = max_sum / left;
        }
        if (flag)
            prod *= val;
    }

    return prod;
}


int main()
{
    cin >> k;
    arr = vector<ld> (k);
    for (int i = 0; i < k; i++)
        cin >> arr[i];
    cin >> s;
    nextes.resize(s.size());
    stack<int> opens;
    vector<ld> maxis;
    char sign = '+';
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            opens.push(i);
        else if (s[i] == ')') {
            int idx = opens.top();
            opens.pop();
            nextes[idx] = i;
        }
    }

    int cnt = 0;

    cout << fixed << setprecision(10) << dfs(0, s.size() - 1) << "\n";

    return 0;
}

• 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