[Heackerrank] [IOI] Guardians of the Lunatics

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [IOI] Guardians of the Lunatics
Source            : Hackerrank
Category          : Dynamic Programing Optimization
Algorithm         : Divide and Conquer Optimization
Verdict           : Accepted

#include <bits/stdc++.h>  
 
using namespace std;  
 
#define ll long long  
 
/********************************************************** 
                 TLE 
 
ll dp[800+5][8000+5];  // dp[ Guard ][ partition to 1 - ] 
bool vis[800+5][8000+5]; 
ll sum[8000+5];   // store cummulative sum 
ll crazy[8000+5]; 
 
int L, G; 
 
ll cost(int a, int b)    // get the result of arr[a...b] 
{ 
    if (a > b) return 0; 
    return (sum[b]-sum[a-1])*(b-a+1); 
} 
 
ll solve(int guard, int pos) 
{ 
    if (guard == 1) return cost(1, pos); 
    if (vis[guard][pos] == 1) return dp[guard][pos]; 
    vis[guard][pos] = 1; 
    ll ret = 1e18; 
    for (int k = 0; k <= pos; k++)  // k=0 for whole part  
        ret = min(ret, solve(guard-1, k) + cost(k+1, pos)); 
    return dp[guard][pos] = ret; 
}
***********************************************************/  
 
ll dp[800+8][8000+8];  
int optimalPos[800+8][8000+8];  
bool vis[800+8][8000+8];  
ll crazy[800+8];  
ll sum[800+8];  
 
int L, G;  
 
ll cost(int a, int b)  
{  
    return a>b ? 0 : (sum[b]-sum[a-1])*(b-a+1);  
}  
 
void solve(int guard, int left, int right, int p1, int p2)  
{  
    if (left > right) return;  
    int mid = (left+right)>>1;  
    dp[guard][mid] = 1e17;  
    optimalPos[guard][mid] = -1; 
    for (int k = p1; k <= p2; k++)  
    {  
        ll wgt = dp[guard-1][k] + cost(k+1, mid);  
        if (dp[guard][mid]>wgt)  
        {  
            dp[guard][mid] = wgt;  
            optimalPos[guard][mid] = k;  
        }  
    }  
    solve(guard, left, mid-1, p1, optimalPos[guard][mid]);  
    solve(guard, mid+1, right, optimalPos[guard][mid], p2);  
}  
 
int main()  
{  
    //freopen("in.txt", "r", stdin);  
 
    cin >> L >> G;  
    for (int i = 1; i <= L; i++)  
    {  
        cin >> crazy[i];  
        sum[i] = sum[i-1] + crazy[i];  
    }  
    for (int i = 1; i <= L; i++)  // initialize  
    {  
        dp[1][i] = cost(1, i);  
    }  
    for (int g = 2; g <= G; g++)  
    {  
        solve(g, 1, L, 1, L);  
    }  
    cout << dp[G][L] << endl;  
}