anushka_me's blog

By anushka_me, history, 26 hours ago, In English

[submission:296009471][problem:1420C1]Hey Codeforces army..

I am stuck in this problem 1420 C1 : Pokemon Army (Easy version)

Approach : for every index i , i either pick the element and afterwards based on the previous index i add it or subtract else i do not pick the element. Here is my solution:

include <bits/stdc++.h>

using namespace std;

long long int call(vector<vector> &dp,vector arr,long long int idx, long long int state,long long int n){ if(idx>n) return 0; if(dp[idx][state]!=-1) return dp[idx][state];

int a=0, b = call(dp,arr,idx+1,state,n);
if(state ==1){
    a = arr[idx];
}else{
    a= -arr[idx];
}
a += call(dp,arr,idx+1,!state,n);
return dp[idx][state] = max(a,b);

} int main(){ int t; cin>>t; for(int i=0;i<t;i++){ long long int n,q; cin>>n>>q; vector arr(n+1,0); for(int j=0;j<n;j++) cin>>arr[j]; vector<vector> dp(n+1,vector(2,-1)); long long int ans = call(dp,arr,0,1,n); cout<<ans<<endl;

}
return 0;

}

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by anushka_me (previous revision, new revision, compare).

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

vector<long long int> arr should be vector<long long int>& arr
and also there's int overflow
int a=0, b = call(dp,arr,idx+1,state,n) should be long long a=0, b = call(dp,arr,idx+1,state,n)

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much dude, I was stuck on it over a month. All the best to you on your CP journey.

    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you just missed the memory thing in that question. same array copied in every instance of function rather than just using the same reference again and again which creates time limit.