HackerEarth- Once Upon A Time in Time-Land (Dynamic Problem Solution)

Once Upon A Time in Time-Land (HackerEarth)

Dynamic Programming, Easy,Algorithms :

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<=b;i++)
#define MAX 10010
#define ll long long
ll arr[MAX];

int main()
{
    int tc;
    int N,K,i,j;
    cin>>tc;
    while(tc--)
    {
        ll max_val=INT_MIN;
        ll Answer=INT_MIN;
        cin>>N>>K;
        f(i,1,N)
        {
            cin>>arr[i];
            if(arr[i]>Answer)
                Answer=arr[i];
        }
        max_val=arr[1];
        j=2;

        f(i,K+2,N)
        {
            if(max_val>0)
            {
                arr[i]+=max_val;
                if(arr[i]>Answer)
                    Answer=arr[i];
            }
            if(arr[j]>max_val)
                max_val=arr[j];
            j++;
        }
        if(Answer<0)
        Answer=0;
        cout<<Answer<<endl;
    }
    return 0;

}

HackerEarth- Xsquare And Chocolates Bars (Dynamic Problem Solution)

XSquare And Chocolate Bars (HackerEarth)

Dynamic Programming, Easy

Solution:-

#include<bits/stdc++.h>

using namespace std;

#define MAX_LEN 1000010

int arr[MAX_LEN];

string B;

char temp;

void init(int len)

{

    for(int i=0;i<=len;i++)

        arr[i]=0;

}

int cal_max(string B,int len)

{

    init(len);

    if(len<3)

        return len;

    int g_max=0;

    bool flag=B[0]==B[1];

    for(int i=2;i<len;i++)

    {

        if(!(B[i]==B[i-1] && flag))

            arr[i]=3+(i-3>=0?arr[i-3]:0);

        flag=B[i]==B[i-1];

        if(g_max<arr[i])

            g_max=arr[i];

    }

    return len-g_max;

}

int main()

{

    int tc,i,len,ans,j;

    cin>>tc;

    while(tc--)

    {

        cin>>B;

        len=B.length();

        cout<<cal_max(B,len)<<endl;

    }

    return 0;

}

HackerEarth- Xsquare And Two Arrays (Dynamic Problem Solution)

Xsquare And Two Arrays (HackerEarth)

Dynamic Programming, Easy;

Solution:-

#include<iostream>

using namespace std;

#define MAX 1000010

#define ll long long

#define f(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i<=b;i+=2)

ll arrA[MAX],arrB[MAX];

ll cal_sum(int start,int left,int right)

{

    if(start==1)

    {

        if(left%2)

            return arrA[right]-arrA[left-1];

        else

            return arrB[right]-arrB[left-1];

    }

    else

    {

        if(left%2==0)

            return arrA[right]-arrA[left-1];

        else

            return arrB[right]-arrB[left-1];

    }

}

int main()

{

    int N,Q;

    cin>>N>>Q;

    int i,j;

    arrA[0]=arrB[0]=0;

    f(i,1,N)

        cin>>arrA[i];

    f(i,1,N)

        cin>>arrB[i];

    fd(i,2,N)

        swap(arrA[i],arrB[i]);

    f(i,2,N)

    {

        arrA[i]+=arrA[i-1];

        arrB[i]+=arrB[i-1];

    }

    int start,left,right;

    f(i,0,Q-1)

    {

        cin>>start>>left>>right;

        cout<<cal_sum(start,left,right)<<endl;

    }

    return 0;

}