Submission #202046

#	Time	Username	Problem	Language	Result	Execution time	Memory
202046		SamAnd	Kvalitetni (COCI16_kvalitetni)	C++17	120 / 120	18 ms	2040 KiB

kvalitetni

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int K = 55, N = 1000006;

int k;
int zz[K];
long double z[K];

int n;
char a[N];

int rr[N];

long double solv(int l, int r)
{
    if (l + 1 == r - 1)
    {
        return z[1];
    }
    vector<pair<int, int> > v;
    int ll = l + 1;
    while (1)
    {
        if (ll > r)
            break;
        v.push_back(m_p(ll, rr[ll]));
        ll = rr[ll] + 2;
    }
    vector<long double> ans;
    for (int i = 0; i < v.size(); ++i)
        ans.push_back(solv(v[i].first, v[i].second));
    char g = a[v[0].second + 1];
    if (g == '+')
    {
        long double yans = 0;
        for (int i = 0; i < v.size(); ++i)
            yans += ans[i];
        return min(yans, z[v.size()]);
    }
    else
    {
        long double sum = 0;
        for (int i = 0; i < v.size(); ++i)
            sum += ans[i];
        if (sum > z[v.size()])
        {
            sort(ans.begin(), ans.end());
            for (int i = ans.size() - 1; i >= 0; --i)
            {
                if (i == 0)
                {
                    for (int j = 0; j < ans.size(); ++j)
                        ans[j] = (z[v.size()] / (ans.size() - i));
                    break;
                }
                if ((sum - (ans.size() - i) * (ans[i] - ans[i - 1])) > z[v.size()])
                {
                    sum = (sum - (ans.size() - i) * (ans[i] - ans[i - 1]));
                }
                else
                {
                    for (int j = i; j < ans.size(); ++j)
                        ans[j] = ans[i];
                    for (int j = i; j < ans.size(); ++j)
                        ans[j] -= (sum - z[v.size()]) / (ans.size() - i);
                    break;
                }
            }
        }
        long double yans = 1;
        for (int i = 0; i < ans.size(); ++i)
            yans *= ans[i];
        return yans;
    }
}

int main()
{
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(9);
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i)
    {
        scanf("%d", &zz[i]);
        z[i] = zz[i];
    }
    scanf(" %s", a);
    n = strlen(a);
    stack<int> s;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == '(')
        {
            s.push(i);
        }
        else if (a[i] == ')')
        {
            rr[s.top()] = i;
            s.pop();
        }
    }
    cout << solv(0, n - 1) << endl;
    return 0;
}

Compilation message (stderr)

kvalitetni.cpp: In function 'long double solv(int, int)':
kvalitetni.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
kvalitetni.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); ++i)
                         ~~^~~~~~~~~~
kvalitetni.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); ++i)
                         ~~^~~~~~~~~~
kvalitetni.cpp:53:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = 0; j < ans.size(); ++j)
                                     ~~^~~~~~~~~~~~
kvalitetni.cpp:63:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = i; j < ans.size(); ++j)
                                     ~~^~~~~~~~~~~~
kvalitetni.cpp:65:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = i; j < ans.size(); ++j)
                                     ~~^~~~~~~~~~~~
kvalitetni.cpp:72:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans.size(); ++i)
                         ~~^~~~~~~~~~~~
kvalitetni.cpp: In function 'int main()':
kvalitetni.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
kvalitetni.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &zz[i]);
         ~~~~~^~~~~~~~~~~~~~
kvalitetni.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", a);
     ~~~~~^~~~~~~~~~

• 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