### sumantopal07's blog

By sumantopal07, 6 weeks ago, ,

https://www.hackerrank.com/contests/pasc-dp/challenges/contiguous-maximization My approach to this problem was to calculate maximum sum of each length sub-array's of each row separately and then use the length as weight and sum as price make it work like the way knapsack works. But issue is that i'am facing wrong answers in large test cases and not able to figure out why am i getting WRONG ANSWER. Any help would be really helpful

My submission

• 0

 » 6 weeks ago, # | ← Rev. 2 →   +21 You should understand that competitive programming isn't always about trying to convert the problem to the most classical problem you know, but rather applying the concepts you learn from solving classical problems to the new one. Why doesn't your approach work? Simply because it opens the possibility of taking multiple segments or even multiple of the same item from the same row, which is clearly forbidden. What should you do instead? Maybe read the editorial whose sole purpose is to help you in these situations Read the short summary I will provide below Let $dp[i][j]$ represent the maximum attainable sum from the first $i$ days with $j$ lectures already attended. Transition is as straightforward as it gets:$dp[i][j] = \max\limits_{0 \le sz \le M} dp[i - 1][j - sz] + f(i, sz)$where $f(i, sz)$ represents the maximum sum of a contiguous subarray of size $sz$ on day $i$. Hopefully you are capable enough to implement this in $O(NM^2)$.
•  » » 6 weeks ago, # ^ |   0 thanks. this help me to change my mindset on competitive programming
•  » » 6 weeks ago, # ^ |   0 Your rating graph is motivational <3
 » 6 weeks ago, # | ← Rev. 2 →   0 Final Bottom-Up Solution is anyone looking for reference. code#include using namespace std; #define int long long #define F first #define S second #define _READ freopen("input.txt", "r", stdin); #define _FAST \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); const int mod = 1e9 + 7; void max_self(int &a,int b) { a=max(a,b); } int32_t main() { //_READ int n,m,w; cin>>n>>m>>w; vector> ar(n,vector(m,0)); vector> dp(n+1,vector(max(w+1,m+1),0)); for(auto &i:ar) for(auto &j:i) cin>>j; vector> items(n,vector(m+1,0)); for(int i=0;i prefix(m,0); prefix[0]=ar[i][0]; for(int j=1;j=1) max_self(items[i][k-j+1],prefix[k]-prefix[j-1]); else if(j==0) max_self(items[i][k-j+1],prefix[k]); } } } // for(int i=0;i=0 && j-k<=w) max_self(dp[i][j],dp[i-1][j-k]+items[i][k]); } } for(int j=w+1;j<=m;j++) dp[i][j]=dp[i][j-1]; } // for(auto &i:dp) // { // for(auto &j:i) // cout<