piya210
December 31, 2014, 3:18am
20
why this code is showing sigsegv error??
can any body answer??
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
int n,x,y,ans,i,j,p,q;
cin>>n>>x>>y;
int a[n],b[n];
int dp[n+1][x+1];
for(i=0;i<=n;i++)
{
for(j=0;j<=x;j++)
{
dp[i][j]=0;
}
}
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
}
for(i=1;i<=n;i++)
{
dp[i][0] = dp[i-1][0] + b[i-1];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=x&&j<=i;j++)
{
p=0;
if(j<=x)
{
p = dp[i-1][j-1]+a[i-1];
}
q=0;
if((i-j)<=y)
{
q = dp[i-1][j]+ b[i-1];
}
dp[i][j]= max(p,q);
}
}
ans = 0;
for(i=0;i<=x;i++)
{
if(dp[n][i]>ans)
ans = dp[n][i];
}
cout<<ans<<endl;
return(0);
}
zstring
December 31, 2014, 7:21am
21
can anyone explain me why greedy technique is giving optimal solution. I am not able to convince myself why greedy is giving optimal solution. I have read the exchange argument, but not able to relate it.
Thanks
ybatra
January 11, 2015, 12:54pm
22
We don’t need below condition at line number 6 in backward dp as It has already been taken care in for loop at line number 4
if (j <= X) {
}
Guys can someone explain me in the test case given in the program andy and bob have 3 orders each
5 3 3
1 2 3 4 5
5 4 3 2 1
Andy can be assigned the last 3 orders of the first row and bob can be assigned the first three orders of the second row.Hence the total comes up to 24 yet we get an o/p of 21 why is that.
I got all the above cases correct but Codechef still shows WA. What could be the reason?
This is the code:
#include<iostream>
#include<vector>
typedef long long int ll;
using namespace std;
ll mem_total(ll N, ll *A, ll *B, ll X, ll Y, ll **mem)
{
if(N==0)
return 0;
if((X>0 && mem[X-1][Y] != 0) && (Y>0 && mem[X][Y-1] != 0))
mem[X][Y] = max(A[N-1] + mem[X-1][Y], B[N-1] + mem[X][Y-1]);
else
mem[X][Y] = max(X>0?(A[N-1]+mem_total(N-1, A, B, X-1, Y, mem)):0,
Y>0?(B[N-1]+mem_total(N-1, A, B, X, Y-1, mem)):0);
}
main()
{
ll N, X, Y;
cin>>N>>X>>Y;
ll **mem;
mem = new ll*[X+1];
for(int i=0; i<=X; i++)
mem[i] = new ll[Y+1];
ll A[N], B[N];
for(ll i=0; i<N; i++)
cin>>A[i];
for(ll i=0; i<N; i++)
cin>>B[i];
mem_total(N, A, B, X, Y, mem);
cout<<mem[X][Y]<<endl;
}
resda
December 28, 2017, 11:24pm
25
a great question ,
make me realize that my DP approach was cyclic and was getting wrong ans.
took me over an hour to figure it our
my code passed all these testcases. still got 10 points
I know it is not a problem, but B[i] cannot be 0
1 Like
my solution passed all the above test cases
can you add the link of your solution?
good question, enjoyed solving it. I couldn’t score but I knew it was dp @dpraveen
which one ? but I know they are wrong.
I was checking for different greedy approaches.
So when SUB[i] equals SUB[i-1] you will check the two arrays (take the maximum). Nice approach, will check it.
Your code returns 14 for:
2 1 1
5 6
6 8
1 Like
ohh i am sorry for that case…@betlista
@rishabhprsd7 : Correct solution should work fine with that, just mentioned
1 Like
@abcdexter24 : I added one more test case (last one), you code returns 14 for this one…
1 Like
emin3m
December 28, 2014, 2:24pm
38
dont check solution…just saw your edit for case 1 and 2