Collect Resources

• Time : $O(nm)$
• Space : $O(m)$

int Solution::solve(vector<vector<int> > &A, vector<vector<int> > &B) {
    long long res = 0, n = A.size(), m = A[0].size();
    long long mod = 1e9 + 7;
    vector<long long> dp(m);
    for(int i = 0; i < n; i++) {
        long long now = 0;
        for(int j = 0; j < m; j++) {
            res += A[i][j];
            now += B[i][j] - A[i][j];
            dp[j] = max(j ? dp[j-1] : 0, now + dp[j]);
        }
    }
    return (res + dp[m-1]) % mod;
}