0 like 0 dislike
3,941 views

| 3,941 views

0 like 0 dislike
```#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
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

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
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;
}