[Spoj] LARMY - Lannister Army

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : LARMY - Lannister Army
Source            : Spoj
Category          : Dynamic Programing Optimization
Algorithm         : Divide and Conquer Optimization
Verdict           : Accepted

Note: Using long long int cause TLE. We can use scanf() too.

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 5000 + 5;  
  
int readInt()  
{  
      bool minus = false;  
      int result = 0;  
    char ch;  
    ch = getchar();  
    while (true)  
    {  
        if (ch == '-') break;  
        if (ch >= '0' && ch <= '9') break;  
        ch = getchar();  
    }  
    if (ch == '-') minus = true; else result = ch-'0';  
    while (true)  
    {  
        ch = getchar();  
        if (ch < '0' || ch > '9') break;  
        result = result*10 + (ch - '0');  
    }  
    if (minus) return -result;  
    else return result;  
}  
  
int n, k;  
int arr[maxn];  
int cost[maxn][maxn];  
int sum[maxn][maxn];  
  
inline void costCalc()  
{  
      for (int i = 1; i <= n; i++)  
      {  
            cost[i][i] = 0;  
            for (int j = i-1; j >= 1; j--)  
            {  
                  cost[j][i] = cost[j+1][i] + (arr[j] > arr[i]);  
            }  
      }  
}  
  
inline void sumCalc()  
{  
      for (int i = 1; i <= n; i++)  
      {  
            sum[i][i] = 0;  
            for (int j = i+1; j <= n; j++)  
            {  
                  sum[i][j] = sum[i][j-1] + cost[i][j];  
            }  
      }  
}  
  
int dp[maxn][maxn];  
int optimalPos[maxn][maxn];  
  
inline void divideConquer(int Partition, int lft, int rgt, int plft, int prgt)  
{  
      if (lft > rgt) return;  
      int mid = (lft + rgt) >> 1;  
      dp[Partition][mid] = 123456789;  
      optimalPos[Partition][mid] = -1;  
      for (int k = plft; k <= prgt; k++)  
      {  
            int cst = dp[Partition-1][k] + sum[k+1][mid];  
            if (cst < dp[Partition][mid])  
            {  
                  dp[Partition][mid] = cst;  
                  optimalPos[Partition][mid] = k;  
            }  
      }  
      divideConquer(Partition, lft, mid-1, plft, optimalPos[Partition][mid]);  
      divideConquer(Partition, mid+1, rgt, optimalPos[Partition][mid], prgt);  
}  
  
int main()  
{  
      n = readInt();  
      k = readInt();  
      for (int i = 1; i <= n; i++) arr[i] = readInt();  
      costCalc();  
      sumCalc();  
      for (int i = 1; i <= n; i++) // base case  
      {  
            dp[1][i] = sum[1][i];  
      }  
      for (int Partition = 2; Partition <= k; Partition++)  
      {  
            divideConquer(Partition, 1, n, 1, n);  
      }  
      printf("%d\n", dp[k][n]);  
}