// C++ program to find Largest Sum Contiguous
// Subarray in a given range with updates
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
#define int long long
// Structure to store
// 4 values that are to be stored
// in the nodes
struct node {
int sum, prefixsum, suffixsum, maxsum;
};
// array to store the segment tree
const int N = 1e5+5;
node tree[4 * N];
// function to build the tree
void build(int arr[], int low, int high, int index)
{
// the leaf node
if (low == high) {
tree[index].sum = arr[low];
tree[index].prefixsum = arr[low];
tree[index].suffixsum = arr[low];
tree[index].maxsum = arr[low];
}
else {
int mid = (low + high) / 2;
build(arr, low, mid, 2 * index + 1);
build(arr, mid + 1, high, 2 * index + 2);
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
tree[index].prefixsum =
max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
tree[index].suffixsum =
max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2 * index + 1].maxsum,
max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
void update(int arr[], int index, int low, int high,
int idx, int value)
{
if (low == high) {
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else {
int mid = (low + high) / 2;
if (idx <= mid)
update(arr, 2 * index + 1, low, mid, idx, value);
else
update(arr, 2 * index + 2, mid + 1,
high, idx, value);
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
tree[index].prefixsum =
max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
tree[index].suffixsum =
max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2 * index + 1].maxsum,
max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
node query(int arr[], int index, int low,
int high, int l, int r)
{
node result;
result.sum = result.prefixsum =
result.suffixsum =
result.maxsum = INT64_MIN;
if (r < low || high < l)
return result;
if (l <= low && high <= r)
return tree[index];
int mid = (low + high) / 2;
if (l > mid)
return query(arr, 2 * index + 2,
mid + 1, high, l, r);
if (r <= mid)
return query(arr, 2 * index + 1,
low, mid, l, r);
node left = query(arr, 2 * index + 1,
low, mid, l, r);
node right = query(arr, 2 * index + 2,
mid + 1, high, l, r);
result.sum = left.sum + right.sum;
result.prefixsum = max(left.prefixsum, left.sum +
right.prefixsum);
result.suffixsum = max(right.suffixsum,
right.sum + left.suffixsum);
result.maxsum = max(result.prefixsum,
max(result.suffixsum,
max(left.maxsum,
max(right.maxsum,
left.suffixsum + right.prefixsum))));
return result;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n>>q;
int T[n],Q[n];
memset(T,0,sizeof(T));
build(T,0,n-1,0);
for(int i=0;i<n;i++)
{
cin>>T[i];
}
for(int i=0;i<n;i++)
{
cin>>Q[i];
}
build(T,0,n-1,0);
int maxi=0;
for(int i=0;i<n;i++)
{
if(Q[i]<0)
{
Q[i]=0;
}
int temp = T[i];
T[i]+=(q*Q[i]);
update(T, 0, 0, n - 1, i, T[i]);
maxi = max(query(T, 0, 0, n - 1, 0, n-1).maxsum,maxi);
T[i]=temp;
update(T,0,0,n-1,i,temp);
}
cout<<maxi<<"\n";
}
return 0;
}
Ly8gQysrIHByb2dyYW0gdG8gZmluZCBMYXJnZXN0IFN1bSBDb250aWd1b3VzCi8vIFN1YmFycmF5IGluIGEgZ2l2ZW4gcmFuZ2Ugd2l0aCB1cGRhdGVzCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZSA8Y3N0ZGludD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgaW50IGxvbmcgbG9uZwovLyBTdHJ1Y3R1cmUgdG8gc3RvcmUKLy8gNCB2YWx1ZXMgdGhhdCBhcmUgdG8gYmUgc3RvcmVkCi8vIGluIHRoZSBub2RlcwpzdHJ1Y3Qgbm9kZSB7CglpbnQgc3VtLCBwcmVmaXhzdW0sIHN1ZmZpeHN1bSwgbWF4c3VtOwp9OwoKLy8gYXJyYXkgdG8gc3RvcmUgdGhlIHNlZ21lbnQgdHJlZQpjb25zdCBpbnQgTiA9IDFlNSs1Owpub2RlIHRyZWVbNCAqIE5dOwoKLy8gZnVuY3Rpb24gdG8gYnVpbGQgdGhlIHRyZWUKdm9pZCBidWlsZChpbnQgYXJyW10sIGludCBsb3csIGludCBoaWdoLCBpbnQgaW5kZXgpCnsKCS8vIHRoZSBsZWFmIG5vZGUKCWlmIChsb3cgPT0gaGlnaCkgewoJCXRyZWVbaW5kZXhdLnN1bSA9IGFycltsb3ddOwoJCXRyZWVbaW5kZXhdLnByZWZpeHN1bSA9IGFycltsb3ddOwoJCXRyZWVbaW5kZXhdLnN1ZmZpeHN1bSA9IGFycltsb3ddOwoJCXRyZWVbaW5kZXhdLm1heHN1bSA9IGFycltsb3ddOwoJfQoJZWxzZSB7CgkJaW50IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CgkJCgkJYnVpbGQoYXJyLCBsb3csIG1pZCwgMiAqIGluZGV4ICsgMSk7CgkJCgkJYnVpbGQoYXJyLCBtaWQgKyAxLCBoaWdoLCAyICogaW5kZXggKyAyKTsKCgkJdHJlZVtpbmRleF0uc3VtID0gdHJlZVsyICogaW5kZXggKyAxXS5zdW0gKwoJCQkJCQl0cmVlWzIgKiBpbmRleCArIDJdLnN1bTsKCgkJdHJlZVtpbmRleF0ucHJlZml4c3VtID0KCQkJCQltYXgodHJlZVsyICogaW5kZXggKyAxXS5wcmVmaXhzdW0sCgkJCQkJdHJlZVsyICogaW5kZXggKyAxXS5zdW0gKwoJCQkJCXRyZWVbMiAqIGluZGV4ICsgMl0ucHJlZml4c3VtKTsKCgkJdHJlZVtpbmRleF0uc3VmZml4c3VtID0KCQkJCQltYXgodHJlZVsyICogaW5kZXggKyAyXS5zdWZmaXhzdW0sCgkJCQkJdHJlZVsyICogaW5kZXggKyAyXS5zdW0gKwoJCQkJCXRyZWVbMiAqIGluZGV4ICsgMV0uc3VmZml4c3VtKTsKCQl0cmVlW2luZGV4XS5tYXhzdW0gPQoJCQkJCW1heCh0cmVlW2luZGV4XS5wcmVmaXhzdW0sCgkJCQkJbWF4KHRyZWVbaW5kZXhdLnN1ZmZpeHN1bSwKCQkJCQltYXgodHJlZVsyICogaW5kZXggKyAxXS5tYXhzdW0sCgkJCQkJbWF4KHRyZWVbMiAqIGluZGV4ICsgMl0ubWF4c3VtLAoJCQkJCXRyZWVbMiAqIGluZGV4ICsgMV0uc3VmZml4c3VtICsKCQkJCQl0cmVlWzIgKiBpbmRleCArIDJdLnByZWZpeHN1bSkpKSk7Cgl9Cn0KCnZvaWQgdXBkYXRlKGludCBhcnJbXSwgaW50IGluZGV4LCBpbnQgbG93LCBpbnQgaGlnaCwKCQkJaW50IGlkeCwgaW50IHZhbHVlKQp7CglpZiAobG93ID09IGhpZ2gpIHsKCQl0cmVlW2luZGV4XS5zdW0gPSB2YWx1ZTsKCQl0cmVlW2luZGV4XS5wcmVmaXhzdW0gPSB2YWx1ZTsKCQl0cmVlW2luZGV4XS5zdWZmaXhzdW0gPSB2YWx1ZTsKCQl0cmVlW2luZGV4XS5tYXhzdW0gPSB2YWx1ZTsKCX0KCWVsc2UgewoKCQlpbnQgbWlkID0gKGxvdyArIGhpZ2gpIC8gMjsKCgkJaWYgKGlkeCA8PSBtaWQpCgkJCXVwZGF0ZShhcnIsIDIgKiBpbmRleCArIDEsIGxvdywgbWlkLCBpZHgsIHZhbHVlKTsKCQllbHNlCgkJCXVwZGF0ZShhcnIsIDIgKiBpbmRleCArIDIsIG1pZCArIDEsCgkJCQloaWdoLCBpZHgsIHZhbHVlKTsKCgkJdHJlZVtpbmRleF0uc3VtID0gdHJlZVsyICogaW5kZXggKyAxXS5zdW0gKwoJCQkJCQl0cmVlWzIgKiBpbmRleCArIDJdLnN1bTsKCgkJdHJlZVtpbmRleF0ucHJlZml4c3VtID0KCQkJCQltYXgodHJlZVsyICogaW5kZXggKyAxXS5wcmVmaXhzdW0sCgkJCQkJdHJlZVsyICogaW5kZXggKyAxXS5zdW0gKwoJCQkJCXRyZWVbMiAqIGluZGV4ICsgMl0ucHJlZml4c3VtKTsKCgkJdHJlZVtpbmRleF0uc3VmZml4c3VtID0KCQkJCQltYXgodHJlZVsyICogaW5kZXggKyAyXS5zdWZmaXhzdW0sCgkJCQkJdHJlZVsyICogaW5kZXggKyAyXS5zdW0gKwoJCQkJCXRyZWVbMiAqIGluZGV4ICsgMV0uc3VmZml4c3VtKTsKCgkJdHJlZVtpbmRleF0ubWF4c3VtID0KCQkJCQltYXgodHJlZVtpbmRleF0ucHJlZml4c3VtLAoJCQkJCW1heCh0cmVlW2luZGV4XS5zdWZmaXhzdW0sCgkJCQkJbWF4KHRyZWVbMiAqIGluZGV4ICsgMV0ubWF4c3VtLAoJCQkJCW1heCh0cmVlWzIgKiBpbmRleCArIDJdLm1heHN1bSwKCQkJCQl0cmVlWzIgKiBpbmRleCArIDFdLnN1ZmZpeHN1bSArCgkJCQkJdHJlZVsyICogaW5kZXggKyAyXS5wcmVmaXhzdW0pKSkpOwoJfQp9Cgpub2RlIHF1ZXJ5KGludCBhcnJbXSwgaW50IGluZGV4LCBpbnQgbG93LAoJCWludCBoaWdoLCBpbnQgbCwgaW50IHIpCnsKCW5vZGUgcmVzdWx0OwoJcmVzdWx0LnN1bSA9IHJlc3VsdC5wcmVmaXhzdW0gPQoJCQkJcmVzdWx0LnN1ZmZpeHN1bSA9CgkJCQlyZXN1bHQubWF4c3VtID0gSU5UNjRfTUlOOwoKCWlmIChyIDwgbG93IHx8IGhpZ2ggPCBsKQoJCXJldHVybiByZXN1bHQ7CgoJaWYgKGwgPD0gbG93ICYmIGhpZ2ggPD0gcikKCQlyZXR1cm4gdHJlZVtpbmRleF07CgoJaW50IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CgoJaWYgKGwgPiBtaWQpCgkJcmV0dXJuIHF1ZXJ5KGFyciwgMiAqIGluZGV4ICsgMiwKCQkJCQltaWQgKyAxLCBoaWdoLCBsLCByKTsKCQkKCWlmIChyIDw9IG1pZCkKCQlyZXR1cm4gcXVlcnkoYXJyLCAyICogaW5kZXggKyAxLAoJCQkJCWxvdywgbWlkLCBsLCByKTsKCglub2RlIGxlZnQgPSBxdWVyeShhcnIsIDIgKiBpbmRleCArIDEsCgkJCQkJbG93LCBtaWQsIGwsIHIpOwoJbm9kZSByaWdodCA9IHF1ZXJ5KGFyciwgMiAqIGluZGV4ICsgMiwKCQkJCQkJbWlkICsgMSwgaGlnaCwgbCwgcik7CgoJcmVzdWx0LnN1bSA9IGxlZnQuc3VtICsgcmlnaHQuc3VtOwoJcmVzdWx0LnByZWZpeHN1bSA9IG1heChsZWZ0LnByZWZpeHN1bSwgbGVmdC5zdW0gKwoJCQkJCQlyaWdodC5wcmVmaXhzdW0pOwoJCQkJCQkJCglyZXN1bHQuc3VmZml4c3VtID0gbWF4KHJpZ2h0LnN1ZmZpeHN1bSwKCQkJCQlyaWdodC5zdW0gKyBsZWZ0LnN1ZmZpeHN1bSk7CglyZXN1bHQubWF4c3VtID0gbWF4KHJlc3VsdC5wcmVmaXhzdW0sCgkJCQkJbWF4KHJlc3VsdC5zdWZmaXhzdW0sCgkJCQkJbWF4KGxlZnQubWF4c3VtLAoJCQkJCW1heChyaWdodC5tYXhzdW0sCgkJCQkJbGVmdC5zdWZmaXhzdW0gKyByaWdodC5wcmVmaXhzdW0pKSkpOwoJCQkJCQoJcmV0dXJuIHJlc3VsdDsKfQoKc2lnbmVkIG1haW4oKQp7CiAgICBpbnQgdDsgCiAgICBjaW4+PnQ7IAogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIGludCBuLHE7CiAgICAgICAgY2luPj5uPj5xOwogICAgICAgIGludCBUW25dLFFbbl07IAogICAgICAgIG1lbXNldChULDAsc2l6ZW9mKFQpKTsKICAgICAgICBidWlsZChULDAsbi0xLDApOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBjaW4+PlRbaV07CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBjaW4+PlFbaV07CiAgICAgICAgfQogICAgICAgIGJ1aWxkKFQsMCxuLTEsMCk7CiAgICAgICAgCiAgICAgICAgaW50IG1heGk9MDsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYoUVtpXTwwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBRW2ldPTA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW50IHRlbXAgPSBUW2ldOwogICAgICAgICAgICBUW2ldKz0ocSpRW2ldKTsKICAgICAgICAgICAgdXBkYXRlKFQsIDAsIDAsIG4gLSAxLCBpLCBUW2ldKTsKICAgICAgICAgICAgbWF4aSA9IG1heChxdWVyeShULCAwLCAwLCBuIC0gMSwgMCwgbi0xKS5tYXhzdW0sbWF4aSk7CiAgICAgICAgICAgIFRbaV09dGVtcDsgCiAgICAgICAgICAgIHVwZGF0ZShULDAsMCxuLTEsaSx0ZW1wKTsKICAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIGNvdXQ8PG1heGk8PCJcbiI7CiAgICB9CglyZXR1cm4gMDsKfQo=