← Real problems

ccc04s5

mediumdpgridStatement on DMOJ

CP Lang

22 lines0.3 spec
// ccc04s5 Super Plumber: from the bottom-left to the bottom-right exit. In each column you
// enter, slide up or down (never through a `*`) collecting digits, then step right. Columns
// are processed right to left: best[r] is the most gold from entering this column at row r.
while true:
    let (rows, cols) = read<(0..=100, 0..=10)>()
    if rows == 0 and cols == 0:
        break
    domain R = 0..rows
    domain C = 0..cols
    let g = read<[R, C]Char>()
    var best: [R]?Int = None
    best[R.last!] = 0
    for c in C.rev:
        fn reach<S: Seq>(path: S) -> yields (k: R, gold: Int):
            var gold = 0
            for k in path.take_while(k => g[k, c] != '*'):
                gold += if g[k, c].is_digit: g[k, c].digit else: 0
                yield (k, gold)
        best = R.map(r => chain(reach(r..), reach((..=r).rev))
            .filter_map(p => best[p.k].map(x => x + p.gold))
            .max()).collect()
    print(best[R.last!]!)

Accepted C++

90 lines · 0.02 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

void solve() {
    int n, m;
    cin >> n >> m;
    if (!n && !m) {
        exit(0);
    }
    string iarr[n];
    for (auto& a : iarr) {
        cin >> a;
    }
    swap(n, m);
    char arr[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            arr[i][j] = iarr[j][i];
        }
    }
    int dp[n + 1][m];
    for (auto& a : dp) {
        fill(a, a + m, -1e9);
    }
    dp[n][m - 1] = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            {
                int cvalue = 0;
                for (int k = j; k < m; k++) {
                    if (arr[i][k] == '*') {
                        break;
                    } else if (isdigit(arr[i][k])) {
                        cvalue += arr[i][k] - '0';
                    }
                    dp[i][j] = max(dp[i][j], cvalue + dp[i + 1][k]);
                }
            }
            {
                int cvalue = 0;
                for (int k = j; k >= 0; k--) {
                    if (arr[i][k] == '*') {
                        break;
                    } else if (isdigit(arr[i][k])) {
                        cvalue += arr[i][k] - '0';
                    }
                    dp[i][j] = max(dp[i][j], cvalue + dp[i + 1][k]);
                }
            }
        }
    }
    cout << dp[0][m - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    while (true) {
        solve();
    }
}