Stuck on spoj Breaking String problem

Revision en1, by PrasoonJha, 2023-05-08 19:06:45

I am using knuth's optimization for solving this problem Spoj Breaking String with given code

int n,m;
        cin>>n>>m;
        vector<int> v(m+2);
        for(int i=1;i<m+1;i++)    cin>>v[i];
        v[m+1] = n;
        sort(v.begin(),v.end());
        vector<vector<int>> dp(m+2,vector<int>(m+2,1e9));
        vector<vector<int>> opt(m+2,vector<int>(m+2,1e4));

        for(int i=0;i<m+2;i++)
        {
            dp[i][i] = 0;
            opt[i][i] = i;
        }

        for(int i = m;i>=0;i--)
        {
            for(int j=i+1;j<m+2;j++)
            {
                int ans = 1e9;
                for(int k = opt[i][j-1];k<=min(j-1,opt[i+1][j]);k++)
                {
                    //cout<<dp[i][k]+dp[k][j]+(v[j]-v[i])<<"\n";
                    if(ans>=(dp[i][k]+dp[k][j]+(v[j]-v[i])))
                    {
                        ans = (dp[i][k]+dp[k][j]+(v[j]-v[i]));
                        opt[i][j] = k;
                    }
                }
                if(ans!=1e9)    dp[i][j] = ans;
                else
                {
                    dp[i][j] = 0;
                    opt[i][j] = i;
                }
            }
        }
        cout<<dp[0][m+1]<<"\n";

I have already defined int as long long.

It is giving WA I have tried everything but unable to find issue please tell me if I am doing something wrong here.

Tags spoj, knuth optimization, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English PrasoonJha 2023-05-08 19:06:45 1498 Initial revision (published)