# TLE in KNPSK by 0.01 Seconds

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?

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