I have done it with normal Knapsack logic with some optimisations but I am
getting TLE
here is my code :
#include<bits/stdc++.h>
#define pp pair<int,int>
#define f first
#define sc second
#define s(t) scanf("%d",&t);
using namespace std;
inline int FAST_IO()
{
int xxxx;
char ch;
int Negativity=0;
while (((ch=getchar_unlocked()) < 48 || ch > 57) && ch != '-');
xxxx=0;
if (ch == '-') Negativity=1;
else xxxx = ch-48;
while ((ch=getchar_unlocked()) >= 48 && ch <= 57) xxxx=xxxx*10+ch-48;
if (Negativity) return -xxxx;
else return xxxx;
}
int dp[101][100001];
int main()
{
#ifndef ONLINE_JUDGE
freopen("ip.txt", "r", stdin);
freopen("op.txt", "w", stdout);
#endif
memset(dp,0,sizeof(dp));
int n;
n=FAST_IO();
vector<pp> A(n);
int sum=0;
for(int i=0;i<n;++i)
{
A[i].f=FAST_IO(); A[i].sc=FAST_IO();
sum+=A[i].f*A[i].sc;
}
int sum1=sum;
sum=(sum+1)/2;
for(int i=0;i<=A[0].f;++i)
{
if(i*A[0].sc>sum)
break;
dp[0][i*A[0].sc]=1;
}
for(int i=1;i<n;++i)
{
for(int j=sum;j>=0;--j)
{
if(dp[i-1][j]==1)
{
for(int k=0;k<=A[i].f;++k)
{
if((j+k*A[i].sc)>sum)
break;
if(dp[i][j+k*A[i].sc]==1)
break;
dp[i][j+k*A[i].sc]=1;
}
}
}
}
int ans;
for(int i=sum;i>=0;--i)
{
if(dp[n-1][i]==1)
{
ans=i;
break;
}
}
int ans1=sum1-ans;
ans1=abs(ans1-ans);
printf("%d\n",ans1);
return 0;
}
On Mon, Aug 5, 2013 at 10:56 PM, Guilherme Puglia <[email protected]>wrote:
> Hello Nilesh,
>
> What is your approach on this?
>
> Regards,
>
> Guilherme Puglia
>
>
> On Mon, Aug 5, 2013 at 1:52 PM, Nilesh Mishra <[email protected]>wrote:
>
>> I was trying this spoj ques and I am getting TLE
>> http://www.spoj.com/problems/FCANDY/
>> Any suggestions on how to proceed please...
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> To post to this group, send email to [email protected].
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/google-code/CALmpLLg5HO-GJ6JJehQ4qy_T%3D9ifPj3kvtYSyQwXf2-F6TMQ9g%40mail.gmail.com
>> .
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/CAKfgAVX1mt7Vs5d2o0nOTWHxkOXOOOnu43mh77uefSBHsrG3vQ%40mail.gmail.com
> .
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CALmpLLjRWVPoPrCOxUX21MNcz3Kn%3Dxt%2BFncijhHh_GtkDnCVJw%40mail.gmail.com.
For more options, visit https://groups.google.com/groups/opt_out.
