[InterviewBit] Collect Resources

Collect Resources

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/11/10/PS/interviewbit/collect-resources/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.