You are given two arrays A and B, both with N elements indexed from 1 to N. For some two indices l and r such that 1 ≤ l ≤ r ≤ N, sumA(l, r) is defined as Al + Al+1 + ... + Ar. Similarly, sumB(l, r) is defined as Bl + Bl+1 + ... + Br. The cost of some interval [l, r] is defined as cost(l, r) = min(sumA(l, r), sumB(l, r)).
You are given a number K such that 1 ≤ K ≤ N. Your task is to divide the indices 1, 2, ... N into exactly K contiguous intervals such that the sum of costs of those intervals is minimized, and report this minimum sum of costs.
In other words, you must find some K intervals [l1, r1], [l2, r2], ... [lK, rK] such that the following conditions are met, and report the sum of costs cost(l1, r1) + cost(l2, r2) + ... + cost(lK, rK).
l1 = 1.rK = N.lj ≤ rjfor all1 ≤ j ≤ K.lj+1 = rj + 1for all1 ≤ j < K.cost(l1, r1) + cost(l2, r2) + ... + cost(lK, rK)is as small as possible.
Input Format
The first line contains two integers, N and K.
The second line contains N integers. The i-th integer on this line is Ai.
The third line contains N integers. The i-th integer on this line is Bi.
Output Format
You must print a single integer, the answer.
Scoring
The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.
You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.
Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.
Constraints
2 ≤ N ≤ 105.2 ≤ K ≤ min(N, 500).-109 ≤ Ai ≤ 109for all1 ≤ i ≤ N.-109 ≤ Bi ≤ 109for all1 ≤ i ≤ N.
my code:
include <bits/stdc++.h>
using namespace std;
// Find prefix sums
void computePrefixSums(int arr, int prefixSum,int n) {
prefixSum[0]=arr[0];
for(int i=1;i<n;i++)
{
prefixSum[i]=prefixSum[i-1]+arr[i];
}
}
int getSum(int prefixSum, int l, int r) {
if(l==0)
return prefixSum[r];
return prefixSum[r] - prefixSum[l - 1];
}
int main() {
int n, K;
cin >> n >> K;
int a[n],b[n];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int prefixA[n], prefixB[n];
computePrefixSums(a, prefixA,n);
computePrefixSums(b, prefixB,n);
vector<vector<int>> cost(n, vector<int>(n, 0));
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int sumA = getSum(prefixA, l, r);
int sumB = getSum(prefixB, l, r);
cost[l][r] = min(sumA, sumB);
}
}
vector<vector<int>> dp(K + 1, vector<int>(n, INT_MAX));
dp[0][0] = 0;
for (int k = 1; k <= K; k++) {
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (dp[k - 1][i - 1] != INT_MAX) {
dp[k][j] = min(dp[k][j], dp[k - 1][i - 1] + cost[i][j]);
}
}
}
}
cout << dp[K][n - 1] << endl;
return 0;
}
can someone please tell me what is going wrong