1796D - Maximum Subarray - CodeForces Solution

#include <bits/stdc++.h>
#define let int long long
#define ulet unsigned long long
using namespace std;
#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define test() \
    int t;     \
    cin >> t;  \
    while (t--)
#define test1() \
    int t;      \
    t = 1;      \
    while (t--)
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define mk make_pair
#define pii pair<let, let>
#define all(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define MOD 1000000007
#define imax 10000000000
#define imin -10000000000
let powmod(let x, let y, let p) //Modular Exponentiation
{
    let res = 1;
    x = x % p;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y % 2 == 1)
            res = (res * x) % p;
        y /= 2;
        x = (x * x) % p;
    }
    return res;
}
string dectobin(int x) //Decimal To Binary
{
    string s = "";
    while (x > 0)
    {
        int t = x % 2;
        s.pb(t + '0');
        x /= 2;
    }
    reverse(s.begin(), s.end());
    if (s.compare("") == 0)
        return "0";
    else
        return s;
}
 
let bintodec(string s) //Binary To Decimal
{
    let ans = 0;
    let n = s.size();
    for (let i = n - 1; i >= 0; i--)
    {
        if (s[i] == '1')
            ans += pow(2, n - i - 1);
    }
    return ans;
}
int find(int k, int n)
{
    return ((n & (1 << (k - 1))) >> (k - 1));
}


 
#define mod 1000000007
 
#define fo(i, n) for (let i = 0; i < (n); i++)
#define forr(i, a, b) for (let i = (a); i < (b); i++)
#define fod(i, n) for (let i = (n); i >= 0; i--)
#define F first
#define S second
#define N 998244353
#define e(a, b) fill(a, a + a.size(), b);

int32_t main()
{  
       ios::sync_with_stdio(false);
       cin.tie(NULL);
       test(){
         int n,k,x;
         cin>>n>>k>>x;
         vector<let> v(n);
         fo(i,n)cin>>v[i];
         let ans = 0;
         vector<vector<let>> dp(n+1,vector<let>(k+1,-1e18));
         dp[0][0] = 0;
         // dp[i][j] -> maximum subarray sum over prefix i with exactly j operation being carried out
         // the solution is very similar to maxsubarry sum we will make dp[i][j]  = 0, the moment it becomes negative
         // transition states are 
         // dp[i][j] <- dp[i-1][j] // not applying operation on index i
         // dp[i][j] <- dp[i-1][j-1] //applying the operation on index i;

         let max_sum = 0;
         // curr_sum of classical max subarray sum is analogous to dp[i][j] and everything is exact same even the method

         for(int i = 1;i<=n;i++){
            for(int j=0;j<=min(k,i);j++){
               dp[i][j] = max(dp[i][j],dp[i-1][j]+v[i-1]-x);
               if(j>0)dp[i][j] = max(dp[i][j],dp[i-1][j-1]+v[i-1]+x);
                
                // make you current subarray sum 0 the  moment it becomes negative
                dp[i][j]=max(dp[i][j],0LL);

                if(n-i>=k-j){// there should be atleast k-j elements remain to complete the exact k operationd
                  max_sum = max(max_sum,dp[i][j]);
                }
            }
         } 
         cout<<max_sum<<endl;
       }
       return 0;
}