Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
3,941 views

in Online Assessments by Expert (109,130 points) | 3,941 views

4 Answers

0 like 0 dislike
Best answer
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
ll dp[200005][5];
int main() {
    
    ll n ; 
    cin>>n ;
    ll v ; 
    cin>>v ; 
    
    ll easy[n+1] = {0};
    ll hard[n+1] = {0};
    
    
    ll i = 1 ; 
    while(i<=n){
        
        cin>>easy[i];
        cin>>hard[i];
        i++;
    }
    
    dp[1][1] = easy[1] ; //dp[][1]====easy 
    dp[1][2] = hard[1] ; //dp[][2]=====hrd
    dp[1][3] = 0 ; 
    
    i = 2 ; 
    while(i<=n){
        
        dp[i][1] = easy[i] + max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]));
        dp[i][2] = hard[i] + dp[i-1][3] ; //did nothing on i-1 dy
        dp[i][3] = 0 + max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]));
        
        
        i++;
    }
    
    cout<<max(dp[n][1],max(dp[n][2],dp[n][3]));
    
    
    return 0 ; 
}
by Expert (109,130 points)
selected by
0 like 0 dislike
Similar to Kumar SIr approach:

 

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n;
    cin>>n;
    vector<vector<int>>vec(n,vector<int>(2));
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            cin>>vec[i][j];
        }
    }
    vector<vector<int>>dp(n,vector<int>(3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(i==0){
                if(j==0)
                dp[i][j]=0;
                else if(j==1)
                dp[i][j]=vec[i][0];
                else
                dp[i][j]=vec[i][1];
            }
            else if(j==2)
            dp[i][j]=dp[i-1][0]+vec[i][1];
            else if(j==0)
            dp[i][j]=max(dp[i-1][1],dp[i-1][2]);
            else
            dp[i][j]=max(dp[i-1][1],dp[i-1][2])+vec[i][0];
        }
    }
    cout<<max(dp[n-1][2],dp[n-1][1])<<endl;
    return 0;
}
by (400 points)
0 like 0 dislike

This is my approch of above problem

memoization technique

 

0--not preform any task

1--perform easy task

2--preform hard task

     public static void main(String[] args) {
        System.out.print("hi");
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int type=sc.nextInt();
        int[]ep=new int[n];
        int[]dp= new int[n];
        for(int i=0;i<n;i++) {
            ep[i]=sc.nextInt();
            dp[i]=sc.nextInt();
        }
        
        int[][]dpp=new int[ep.length][3];
        for(int[]d:dpp) {
            Arrays.fill(d, -1);
        }
        System.out.print(check(ep,dp,0,0,dpp));
        
         
    }
    public static int  check(int[]easy,int[]diff,int prev,int i,int[][]dpp) {
        if(i==easy.length) {
            return 0;
        }
        if(dpp[i][prev]!=-1)return dpp[i][prev];
        int notpick=check(easy,diff,0,i+1,dpp);
        
        int easypick=easy[i]+check(easy,diff,1,i+1,dpp);
        int diffpick=Integer.MIN_VALUE;
        if(prev==0) {
            diffpick=diff[i]+check(easy,diff,2,i+1,dpp);
        }
        return  dpp[i][prev]=Math.max(notpick, Math.max(easypick, diffpick));
        
    }

by (140 points)
edited by
0 like 0 dislike

Porblem Description. : 

by Expert (109,130 points)
1 0
sir can we take the hard task amount and sort them and add the max and remove before number and add the number before the number we removed now and soon and add it to the variable
1 0
Thats greedy strategy it will not pass for all cases
1 0
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n;
    cin>>n;
    vector<vector<int>>vec(n,vector<int>(2));
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            cin>>vec[i][j];
        }
    }
    vector<vector<int>>dp(n,vector<int>(3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(i==0){
                if(j==0)
                dp[i][j]=0;
                else if(j==1)
                dp[i][j]=vec[i][0];
                else
                dp[i][j]=vec[i][1];
            }
            else if(j==2)
            dp[i][j]=dp[i-1][0]+vec[i][1];
            else if(j==0)
            dp[i][j]=max(dp[i-1][1],dp[i-1][2]);
            else
            dp[i][j]=max(dp[i-1][1],dp[i-1][2])+vec[i][0];
        }
    }
    cout<<max(dp[n-1][2],dp[n-1][1])<<endl;
    return 0;
}