Calvins Game, INOI 2013

Problem Description

Question : Calvins Game, INOI 2013

Submit Code : Codechef

Prerequisites

Dynamic Programming : 1D

Solution

This problem can be broken into smaller sub-problems. We would have to create two 1D for applying DP. One array (points1[x]) will store maximum points made while making backward phase from square x to square 1, and another (points2[y], where $y \ge k$) will store maximum points made while making forward phase from square k to square y. So, for every $y \ge k$ we will have points made $= points1[y] + points2[y] - square[y]$. Then we will take maximum of those points which will be our answer.

For example, for n = 5, k = 2 , and square[] = {5, 3, -2, 1, 1}

if Calvin make forward move from 2 to 4 and backward phase from 4 to 1 then for forward phase we have points2[4] and backward phase we have points1[4]. So, total points will be $points1[4] + points2[4] - square[4]$

Code

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> squares(n+1);
    for(int i=1;i<=n;i++)
        cin >> squares[i];

    vector<int> points1(n+1);
    points1[1] = squares[1];
    points1[2] = squares[1] + squares[2];
    for(int i=3;i<=n;i++)
        points1[i] = squares[i] + max(points1[i-1], points1[i-2]);

    vector<int> points2(n+1);
    points2[k] = 0;
    points2[k-1] = 0;
    for(int i=k+1;i<=n;i++)
        points2[i] = squares[i] + max(points2[i-1], points2[i-2]);

    int ans = points1[k] + points2[k] - squares[k];
    for(int i=k+1;i<=n;i++)
        ans = max(ans, points1[i] + points2[i] - squares[i]);
    cout << ans;
    return 0;
}