#include <bits/stdc++.h>
using namespace std;
int n,m;
long long arr[100005],brr[100005];
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> arr[i];
for(int i=1; i<=m; i++) cin >> brr[i];
long long dp[n+1][m+1];
for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) dp[i][j]=1e16;
dp[1][1]=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(i==1&&j==1) continue;
dp[i][j]=min(dp[i-1][j]+brr[j],dp[i][j-1]+arr[i]);
}
}
int prev=-1;
for(int i=1; i<=n; i++){
pair<long long,int> opt={1e16,-1};
for(int j=1; j<=m; j++){
opt=min(opt,{dp[i][j],j});
}
assert(opt.second>=prev);
prev=opt.second;
}
cout << dp[n][m];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |