Yup I got it man thanks!
Hi .Can someone please explain the lazy propagation part from the codeforces post "Efficient and easy segment trees" .I have understood the recursive one but I am having difficulty understanding the iterative one as it is given there.So can some one please explain a bit so that it may become a bit easier for me to understand?
I cannot figure out how to check if a difference of diff can be achieved or not efficiently.Can you give some more hints?
I have a doubt .My solution got accepted.If I am not wrong it works in O(n^3).So if max. n is 300 then O(n^3) means 27*10^6 operations.How come this gets accepted in 2 seconds? Is'nt the maximum number of operations that we can perform in 1 second around 10^6? So for 2 seconds should'nt it be 2*10^6?
Thanks a lot! Those were three very good points.I was making some big mistakes.
This is my code .Please check this out.
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef vector<int> vi;//vector<long long int> ar;//const ll mod=1000000007;//map<int,int> mp;int ar[1000005];int dp[1000005];int dpb[1000005];int main(){int n;int k;cin>>n>>k;int i;for(i=1;i<=n;i++){cin>>ar[i];}if(n==1){cout<<0<<endl;
I dont know why I am getting some tests as incorrect.I calculate the forward case as dp[i]=max(dp[i-1],dp[i-2])+ar[i] ,this loop I run from k to n. For backward case I do the same from 1 to n. and then I find the index where I get max(forward+backward) .Please help me out.Can you tell me what is wrong with this approach
Can you please help me out?What I am doing is finding out the index where I'll get the maximum score from k , using dp. And then I am finding out the maximum score I can get at that particular index if I start from 1.Is this approach correct and if not can you tell me what is wrong?