Submission #1163225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163225		Alebn	Kvalitetni (COCI16_kvalitetni)	C++20	0 / 120	1096 ms	5584 KiB

kvalitetni

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <numeric>
#include <cmath>
#include <iomanip>
#define int long long
#define ff first
#define ss second
using namespace std;

int opt(vector<int>& a, int x) {
    priority_queue<int> pq;
    int temp;
    for(auto i : a) pq.push(i);
    while(x--) {
        temp = pq.top();
        pq.pop();
        pq.push(temp - 1);
    }
    int res = 1;
    while(pq.size()) {
        res *= pq.top();
        pq.pop();
    }
    return res;
}
void dfs(vector<pair<bool,vector<int>>>& graph, string& s, int i, int l, int r) {
    int last = l, cnt = 0;
    for(int j = l; j <= r; j++) {
        if(s[j] == '(') cnt++;
        else if(s[j] == ')') {
            cnt--;
            if(!cnt) {
                if(j != r) {
                    if(s[j + 1] == '*') graph[i].ff = true;
                }
                graph[i].ss.push_back(graph.size());
                graph.push_back({false,{}});
                dfs(graph, s, graph.size() - 1, last + 1, j - 1);
                last = j + 2;
            }
        }
    }
}
double dfss(vector<pair<bool,vector<int>>>& graph, vector<int>& a, int i) {
    if(!graph[i].ss.size()) return a[0];
    double res = (graph[i].ff ? 1 : 0), suum = 0, temp;
    vector<int> kak;
    for(auto j : graph[i].ss) {
        temp = dfss(graph, a, j);
        kak.push_back(temp);
        if(graph[i].ff) res *= temp;
        else res += temp;
        suum += temp;
    }
    if(suum > a[graph[i].ss.size()-1]) {
        if(graph[i].ff) {
            return opt(kak, suum - a[graph[i].ss.size()-1]);
        } else return a[graph[i].ss.size()-1];
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    string s;
    cin >> s;
    vector<pair<bool,vector<int>>> graph(1, {false, {}});
    dfs(graph, s, 0, 1, s.size() - 2);
    cout << fixed << setprecision(5) << dfss(graph, a, 0) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12