The problem statement:
Given two arrays
a
andb
with sizesn
andm
respectively. All numbers in these arrays are in the range of 0 to 9 inclusive. Lets create a matrix with size ofn x m
where values in rowi
and columnj
is equal toai * 10^9 + bj
. Find the path from square1,1
ton,m
with the maxium sum. You're allowed to move forward or down.Input parameters: The first line contains
n
andm
(1 <= n, m <= 100 000)The second line contains values of array
a
The third line contains values of array
b
Output Print the maximum sum
Time limit: 1 second
Memory limit: 512MB
Example:
input:
7 4
0 7 1 7 6 7 6
4 1 9 7
output: 55000000068
I tried to solve this problem with dynamic programming, but my solution works in O(n * m)
and can't pass time limit:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n, m; cin >> n >> m;
vector<uint64_t> a(n), b(m);
for(int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
a[i] = tmp * 10e8;
}
for(int i = 0; i < m; i++) cin >> b[i];
vector<uint64_t> dp(m);
dp[0] = a[0] + b[0];
for (int i = 1; i < m; i++)
dp[i] = dp[i-1] + a[0] + b[i];
for (int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if (j == 0)
dp[j] = dp[j] + a[i] + b[j];
else
dp[j] = max(dp[j], dp[j-1]) + a[i] + b[j];
}
}
cout << dp.back() << endl;
return 0;
}