x = int(input())
def cal(n,m,arr):
if m >= n:
t = sum(arr) + n*(m-1) - (n-1)*n//2
return t
t = sum(arr[:m])
k = t
for i in range(n-m):
k -= arr[i]
k += arr[i+m]
t = max(t,k)
return t + m*(m-1) - m*(m-1)//2
for jj in range(x):
n,m = [int(i) for i in input().split(' ')]
arr = [int(i) for i in input().split(' ')]
print(cal(n,m,arr))#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
int lowbit(int x)
{
return x & -x;
}
// int query(vector<int> tree, int node, int ns, int ne, int qs, int qe)
// {
// int ans = 0;
// if (qe < ns || qs > ne) return ans;
// if (qe <= ns && qs >= ne) return tree[node];
// }
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) cin >> a[i];
vector<int> prevfixSum(n + 1, 0);
for (int i = 1; i <= n; i ++ ) prevfixSum[i] = prevfixSum[i - 1] + a[i - 1];
int ans = 0;
if (k < n){
ans = prevfixSum[k];
for (int i = k + 1; i <= n; i ++ ) ans = max(ans, prevfixSum[i] - prevfixSum[i - k]);
cout << ans + k * (k - 1) / 2 << endl;
return;
}
cout << prevfixSum[n] + (k - 1 + k - n) * n / 2 << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _T;
cin >> _T;
while (_T -- )
{
solve();
}
return 0;
}214A - System of Equations | 287A - IQ Test |
1108A - Two distinct points | 1064A - Make a triangle |
1245C - Constanze's Machine | 1005A - Tanya and Stairways |
1663F - In Every Generation | 1108B - Divisors of Two Integers |
1175A - From Hero to Zero | 1141A - Game 23 |
1401B - Ternary Sequence | 598A - Tricky Sum |
519A - A and B and Chess | 725B - Food on the Plane |
154B - Colliders | 127B - Canvas Frames |
107B - Basketball Team | 245A - System Administrator |
698A - Vacations | 1216B - Shooting |
368B - Sereja and Suffixes | 1665C - Tree Infection |
1665D - GCD Guess | 29A - Spit Problem |
1097B - Petr and a Combination Lock | 92A - Chips |
1665B - Array Cloning Technique | 1665A - GCD vs LCM |
118D - Caesar's Legions | 1598A - Computer Game |