oj.uz

Submission #202046

# Submission time Handle Problem Language Result Execution time Memory
202046 2020-02-13T08:45:36 Z SamAnd Kvalitetni (COCI16_kvalitetni) C++17
120 / 120
 18 ms 2040 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 11 ms 1404 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1144 KB Output is correct
2 Correct 15 ms 2040 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1016 KB Output is correct
2 Correct 18 ms 1912 KB Output is correct