Laskutoimitus

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define D(x) {x;}
#else
#define D(x)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const ll M = 1e9+7;
const int N = 5001;

string s;

int dp[N][N];

int lstpm[N], lsts[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);
    cin >> s;
    int n = sz(s);
    int fpm = -1, fs = -1;
    for (int i = 0; i < sz(s); ++i) {
        if (s[i] == '+' || s[i] == '-') fpm = i;
        lstpm[i] = fpm;
        if (s[i] == '*') fs = i;
        lsts[i] = fs;
    }

    if (fpm == -1 && fs == -1) {
        ll res = 0;
        ll mu = 0;
        for (int i = n-1; i >= 0; --i) {
            mu *= 10;
            mu += 1;
            mu %= M;
            res += ll(i+1) * (s[i]-'0') * mu % M;
            res %= M;
        }
        cout << res << endl;
        return 0;
    }

    ll res = 0;
    for (int l = 0; l < n; ++l) {
        if (s[l] >= '0' && s[l] <= '9') {
            dp[l][l] = s[l]-'0';
            res += dp[l][l];
        }
    }
    for (int w = 2; w <= n; ++w) {
        D(cout << w << endl);
        for (int l = 0; l+w <= n; ++l) {
            int r = l+w-1;
            if (s[l] < '0' || s[l] > '9' || s[r] < '0' || s[r] > '9') continue;
            int p = lstpm[r];
            if (p >= l) {
                ll sg = s[p] == '+' ? 1 : M-1;
                dp[l][r] = (dp[l][p-1] + sg * dp[p+1][r]) % M;
                goto done;
            }
            p = lsts[r];
            if (p >= l) {
                dp[l][r] = ll(dp[l][p-1]) * dp[p+1][r] % M;
                goto done;
            }
            dp[l][r] = (10ll * dp[l][r-1] + dp[r][r]) %M;
done:
            D(cout << s.substr(l, w) << " " << dp[l][r] << endl);
            res += dp[l][r];
            res %= M;
        }
    }
    cout << res << endl;
}

Test 1

Group: 1, 2, 6

Verdict: ACCEPTED

Test 2

Group: 1, 2, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 2, 6

Verdict: ACCEPTED

Test 5

Group: 2, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 7

Group: 6

Verdict: RUNTIME ERROR

Test 8

Group: 6

Verdict: RUNTIME ERROR

Test 9

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 4, 6

Verdict: RUNTIME ERROR

Test 11

Group: 4, 6

Verdict: RUNTIME ERROR

Test 12

Group: 5, 6

Verdict: RUNTIME ERROR

Test 13

Group: 5, 6

Verdict: RUNTIME ERROR