HackerEarth Dynamic DP problem solution

YASH PAL,
In this HackerEarth Dynamic DP problem solution You are given the following:
  1. An array A of length n that contains integers
  2. DP of length n 
  3. Arrays L and R of length n that contain integers
You are also provided with the following attributes:
  1. If i = 1, then Li = Ri = 1
  2. If 2 <= i <= n, then 1 <= Li <= Ri < i
  3. DP1 = A1
  4. DPi = min(DP[Li,Ri]) + Ai
The element A[x,y] is defined to be all the elements that are available in [a,b] of array A. For example, DP[2,3] indicates DP2 and DP3.
You are also provided with  queries that state the following:
  1. You are given two integers x and y.
  2. You are required to replace DP[1,x] to y and then update the remaining part of DP. Now, print DPn.
HackerEarth Dynamic DP problem solution

HackerEarth Dynamic DP problem solution.

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>

using namespace std;
#define ll long long
#define pii pair<int,int>

bool debug=true;

set<pii> st;
bool stand=true;
ll n,m,q;
ll ans;
int main(int argc,char* argv[]){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=0;i<q;i++){
        int mode;
        scanf("%d",&mode);
        if(mode==1){
            int x,y;
            scanf("%d%d",&x,&y);
            set<pii>::iterator pos=st.find(make_pair(x,y));
            if(pos!=st.end()){
                st.erase(pos);
                if(stand){
                    ans--;
                }else{
                    ans++;
                }
            }else{
                st.insert(make_pair(x,y));
                if(stand){
                    ans++;
                }else{
                    ans--;
                }
            }
        }else{
            ans=n*m-ans;
            stand=!stand;
        }
    }
    
    cout<<ans;
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14;
const ll inf = 1e18;
 

int n, a[maxn], l[maxn], r[maxn];
ll b[maxn];
multiset<ll> s;
vector<ll> add[maxn], rem[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> l[i] >> r[i], l[i]--, r[i]--;
    for(int i = n - 1; i >= 0; i--){
        for(auto x : add[i])
            s.insert(x);
        if(i != n - 1)
            b[i] = s.size() ? *s.begin() : inf;
        if(i){
            add[ r[i] ].push_back(b[i] + a[i]);
            rem[ l[i] ].push_back(b[i] + a[i]);
        }
        for(auto x : rem[i])
            s.erase(s.find(x));
    }
    for(int i = 1; i < n; i++)
        b[i] = min(b[i - 1], b[i]);
    int q;
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        cout << b[x - 1] + y << 'n';
    }
}
coding problems