SPOJ – LKS – Large Knapsack

#include<stdio.h>
typedef int ll;
ll max(ll a,ll b)
{
 if(a>b)
 return a;
 else return b;
}
ll ts,n;
ll w[505],v[505];
ll dp[2][2000002];
int main()
{
 scanf("%d%d",&ts,&n);
 ll i;
 for(i=1;i<=n;i++)
 scanf("%d%d",&v[i],&w[i]);
 ll j;
 ll cur=1,prev=0;
 for(i=1;i<=n;i++)
 {
 for(j=0;j<=ts;j++)
 {
 if(j==0)
 dp[cur][j]=0;
 else
 {
 if(w[i]<=j)
 dp[cur][j]=max(v[i]+dp[prev][j-w[i]],dp[prev][j]);
 else
 dp[cur][j]=dp[prev][j];
 }
 }
 cur=1-cur;
 prev=1-prev;
 }
 printf("%d\n",dp[n&1][ts]);
}