Diksha_goyal's blog

By Diksha_goyal, history, 4 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Your code is copying the vectors v and dp with every recursive call. Try passing them by reference or declaring marbles and dp before the lambda-expression so that they can be captured and used inside of it.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Most of the variables passed in the function could've been declared outside, it makes the function calls easier to write, when there are 2 arguments instead of 10.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Accepted solution