I am following the same approach explained by @gkcs, here: CodeChef Long Challenge - FEB17 - INTERVAL - YouTube
Here is my code solution to the problem:
I am getting TLE for test cases 5 to 9.
#include<bits/stdc++.h>
#define MAX_N 300001
#define MAX_M 201
using namespace std;
int main(void) {
long long t, n, m;
long long x;
long long b[MAX_M];
long long c[MAX_N];
long long dp[MAX_N][MAX_M];
long long cum_sum, i, j, optimalScore;
scanf("%lld", &t);
deque<long long> dq;
while (t-- ) {
scanf("%lld%lld",&n, &m);
cum_sum = 0;
for (i = 1; i <= n; i++ ) {
scanf("%lld",&x);
cum_sum += x;
c[i] = cum_sum;
}
for (i = 1; i <= m; i++ ) {
scanf("%lld",&b[i]);
}
long long lastIndex = n - b[m] + 1;
long long cum_start, cum_end;
for (i = 1; i <= lastIndex; i++ ) {
cum_end = c[i + b[m] - 1];
if ( (i-1) >= 1) {
cum_start = c[i - 1];
}
else {
cum_start = 0;
}
dp[i][m] = cum_end - cum_start;
}
for (i = (m-1) ; i >= 1; i-- ) {
lastIndex = n - b[i] + 1;
long long slidingWindowSize = b[i] - b[i+1] - 1;
dq.clear();
for (long long k = 1; k <= slidingWindowSize; k++ ) {
while((!dq.empty()) && ( dp[1+k][i+1] >= dp[dq.back()][i+1] ) ) {
dq.pop_back();
}
dq.push_back(1+k);
}
cum_end = c[1 + b[i] - 1];
cum_start = 0;
dp[1][i] = cum_end - cum_start;
dp[1][i] -= dp[dq.front()][i+1];
for ( j = 2; j <= lastIndex; j++) {
// calc the sum
cum_end = c[j + b[i] - 1];
cum_start = c[j - 1];
dp[j][i] = cum_end - cum_start;
//add the new element to the dq
while ((!dq.empty()) && ( dq.front() < (j+1)) ) {
dq.pop_front();
}
while ( (!dq.empty()) && ( dp[j+slidingWindowSize][i+1] >= dp[dq.back()][i+1] ) ) {
dq.pop_back();
}
dq.push_back(j+slidingWindowSize);
// subtract the max possible score of opponent
dp[j][i] -= dp[dq.front()][i+1];
}
}
optimalScore = dp[1][1];
for (i = 2; i <= lastIndex; i++ ) {
if (dp[i][1] > optimalScore) {
optimalScore = dp[i][1];
}
}
printf("%lld\n",optimalScore);
}
return 0;
}