oj.uz

Submission #202045

# Submission time Handle Problem Language Result Execution time Memory
202045 2020-02-13T08:41:24 Z SamAnd Kvalitetni (COCI16_kvalitetni) C++17
108 / 120
 18 ms 2424 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];
        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:51:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < ans.size(); ++j)
                                 ~~^~~~~~~~~~~~
kvalitetni.cpp:61:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = i; j < ans.size(); ++j)
                                 ~~^~~~~~~~~~~~
kvalitetni.cpp:63:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = i; j < ans.size(); ++j)
                                 ~~^~~~~~~~~~~~
kvalitetni.cpp:69: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:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
kvalitetni.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &zz[i]);
         ~~~~~^~~~~~~~~~~~~~
kvalitetni.cpp:86: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 380 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 380 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 508 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 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 1528 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 13 ms 1656 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1144 KB Output is correct
2 Correct 18 ms 2424 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 888 KB Output is correct
2 Correct 15 ms 2296 KB Output is correct