oj.uz

Submission #130470

# Submission time Handle Problem Language Result Execution time Memory
130470 2019-07-15T09:21:35 Z forestryks Kvalitetni (COCI16_kvalitetni) C++14
120 / 120
 15 ms 1284 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define left left123
#define right right123

const int MAXN = 1e6 + 5;
int n, m;
string s;
ld z[55];

ld rec(int &ptr) {
    assert(s[ptr++] == '(');
    ld ret = 0;
    if (s[ptr] == '?') {
        ptr++;
        ret = z[0];
    } else {
        vector<ld> a = {};
        a.push_back(rec(ptr));
        if (s[ptr] == '*') {
            while (s[ptr] == '*') {
                ptr++;
                a.push_back(rec(ptr));
            }

            ld s = 0;
            ld mx = z[(int)a.size() - 1];
            vector<pair<ld, int>> t;
            rep(i, a.size()) {
                s += a[i];
                t.push_back({a[i], 1});
            }

            // cout << s << ' ' << mx << endl;
            // rep(i, a.size()) {
            //     cout << a[i] << ' ';
            // }
            // cout << endl;

            sort(all(t));

            // rep(i, t.size()) {
            //     cout << "{" << t[i].f << ' ' << t[i].s << "} ";
            // }
            // cout << endl;

            while (s > mx) {
                int k = (int)t.size() - 1;
                assert(k >= 0);
                ld d = (k == 0 ? t[k].f : t[k].f - t[k - 1].f);

                ld c = min(d, (s - mx) / t[k].s);
                s -= c * t[k].s;
                t[k].f -= c;

                if (c < d) {
                    break;
                } else {
                    if (k != 0) t[k - 1].s += t[k].s;
                    t.pop_back();
                }
            }

            // rep(i, t.size()) {
            //     cout << "{" << t[i].f << ' ' << t[i].s << "} ";
            // }
            // cout << endl;

            ret = 1;
            rep(i, t.size()) {
                rep(j, t[i].s) {
                    ret *= t[i].f;
                }
            }
        } else {
            ret += a[0];
            while (s[ptr] == '+') {
                ptr++;
                a.push_back(rec(ptr));
                ret += a.back();
            }
            ret = min(ret, z[(int)a.size() - 1]);
        }
    }

    assert(s[ptr++] == ')');
    return ret;
}

int main() {
    FAST_IO;
    cin >> m;
    rep(i, m) {
        cin >> z[i];
    }
    cin >> s;
    n = s.size();

    cout.precision(20);
    cout.setf(ios::fixed);
    int ptr = 0;
    cout << rec(ptr) << endl;
}

Compilation message

kvalitetni.cpp: In function 'ld rec(int&)':
kvalitetni.cpp:9:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
                                     ~~~~^~~~~
kvalitetni.cpp:40:13: note: in expansion of macro 'rep'
             rep(i, a.size()) {
             ^~~
kvalitetni.cpp:9:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
                                     ~~~~^~~~~
kvalitetni.cpp:81:13: note: in expansion of macro 'rep'
             rep(i, t.size()) {
             ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

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

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 10 ms 900 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 892 KB Output is correct
2 Correct 15 ms 1284 KB Output is correct

Subtask #10
12.0 / 12.0

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