Submission #130470

#	Time	Username	Problem	Language	Result	Execution time	Memory
130470		forestryks	Kvalitetni (COCI16_kvalitetni)	C++14	120 / 120	15 ms	1284 KiB

kvalitetni

#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 (stderr)

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 / 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