TLE in KNPSK by 0.01 Seconds

general
, , , , ,
1

Here is my code for the KNPSK problem:-

#include <bits/stdc++.h>
using namespace std;

int knpsk(int w[], int v[], int n, int t)
{
    int i, j;
    int dp[n+1][t+1];
    for(i=0; i<=n; i++)
    {
        for(j=0; j<=t; j++)
        {
            if(i==0 || j == 0)
                dp[i][j] = 0;
            else if(w[i-1] <= j)
                dp[i][j] = max(v[i-1] + dp[i-1][j-w[i-1]], dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][t];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;

    int W[N], V[N];

    for(int i=0; i<N; i++)
        cin >> W[i] >> V[i];

    int M = 0;
    for(int i=0; i<N; i++)
        M += W[i];

    for(int i=1; i<=M; i++)
        cout << knpsk(W, V, N, i) << " ";

    return 0;
}

This code takes 1.01 seconds to solve the problem whereas the time limit is 1 second. I have tried all possible ways to speed up the execution but this (1.01 seconds) is the best that I could achieve. How do I further optimize the code?

2

Well, if the timelimit is 1 sec then it shows running time as 1.01 no matter how long your code takes to run. The server runs your code for 1.01 seconds and gives the result as TLE.

You need more efficient algorithm to get AC.

2 Likes
3

@ssjgz, @vijju123 and @shadow9 can you please help me optimize my code to avoid TLE and get an AC?

4

@tmwilliamlin can you please help me in tackling this TLE?

5

In your code, u r calling the function M times and the complexity of knpsk() is (n * t) so total complexity becomes (n * t * m) and maximum value of m can be 2 * n, therefore it is giving tle as the complexity increases O(n^2).
You can go through the editorial for optimal approach .
https://discuss.codechef.com/t/knpsk-editorial/5962