Time Limit Exceeded for the recursive DP solution

Revision en2, by Diksha_goyal, 2021-09-19 16:12:01

I'm very much confused, why my memoized solution 129162014 for the problem https://codeforces.com/contest/38/problem/E

#include <bits/stdc++.h>
using namespace std;
 
 
 
int  main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin>>n;
    long long inf = 1e18 + 5;
    auto fun = [&](auto self, vector<pair<int, long long>> v, int n, int pos, int pinned_pos, vector<vector<long long>> dp, long long inf)->long long
    {
        if (pos > n - 1){
            return 0LL;
        }
        if (dp[pos][pinned_pos] != inf){
            return dp[pos][pinned_pos];
        }
 
        long long Selected = v[pos].second + self(self, v, n, pos + 1, pos, dp, inf);
        long long Not_selected = abs(v[pos].first - v[pinned_pos].first) + self(self, v, n, pos + 1, pinned_pos, dp, inf);
        return dp[pos][pinned_pos] = min(Not_selected, Selected);
    };
 
    vector<pair<int, long long> > marbles(n);
    for(int i = 0; i<n; i++){
        cin>>marbles[i].first>>marbles[i].second;
    }
    sort(marbles.begin(), marbles.end());
    vector<vector<long long> > dp(n+1, vector<long long>(n+1, inf));
    long long ans = fun(fun, marbles, n, 1, 0, dp, inf) + marbles[0].second;
    cout<<ans<<'\n';
    return 0;
}

is not working in limited time, I think, its time complexity is reasonably correct for the given constraints... can someone suggest to me, where I'm going wrong and how can you please modify my code so that It can work for the given problem. I'm sorry, for causing trouble, But I'm new to puzzle-solving and I have only you guys when I am stuck in some problem. So, please help me, guys.

Tags c++, dp, subset, memoization, recursion, inclusion-exclusion, sorting, lambda

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Diksha_goyal 2021-09-19 16:12:01 30
en1 English Diksha_goyal 2021-09-19 16:11:32 1706 Initial revision (published)