10819 - Trouble of 13-Dots

[brianfry713]

Try using BufferedWriter.

I solved it in C++
Bottom up DP: 0.136 seconds
Top down DP: 1.136 seconds

So you might have to switch to C++ or bottom up.

[richatibrewal]

I am not getting the required output for this problem. Here is my code:

Code: Select all

Accepted

[brianfry713]

You're printing res twice.

[richatibrewal]

Oops !!! such a silly mistake.

[chachachowdhury]

wa pls help

Code: Select all

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long  ull;

#define     mem(a,b)        memset(a,b,sizeof(a))
#define     mp              make_pair
#define     pii             pair<int,int>
#define     fs              first
#define     sc              second
#define     VI              vector<int>
#define     clr(a)          a.clear()
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-5
#define     sf              scanf
#define     pf              printf
#define     all(a)          a.begin(),a.end()
#define     allr(a)         a.rbegin(),a.rend()
#define     full(a,l)       a,a+l
#define     fread(name)     freopen(name,"r",stdin)
#define     fwrite(name)    freopen(name,"w",stdout)
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount
#define     count_onell     __builtin_popcountll
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9
#define     fore(x,i)       for(typeof((x).begin()) i=(x.begin()); i!=(x).end(); ++i)
#define     rfore(x,i)      for(typeof((x).rbegin()) i=(x.rbegin()); i!=(x).rend(); ++i)
#define     For(i,a,b)      for(int i=a;i<=b;++i)
#define     rFor(i,a,b)     for(int i=a;i>=b;--i)

template<class T> T pwr(T b, T p)
{
    T r=1,x=b;
    while(p)
    {
        if(p&1)r*=x;
        x*=x;
        p=(p>>1);
    }
    return r;
}
template<class T> T lcm(T a,T b)
{
    return(a/__gcd(a,b))*b;
}
template<class T> T sqr(T a)
{
    return a*a;
}
template<class T> void xswap (T &x,T &y)
{
    if(x!=y)
    {
        x^=y;
        y^=x;
        x^=y;
    }
}
template<typename T> inline bool isOn(T &mask,int pos)
{
    return((mask)&(1LL<<pos));
}
template<typename T> inline T setf(T mask,int pos)
{
    return mask=((mask)&(~(1LL<<pos)));
}
template<typename T> inline T sett(T mask,int pos)
{
    return mask=((mask)(1LL<<pos));
}
template<typename T> inline T flip(T mask,int pos)
{
    return mask=((mask)^(1LL<<pos));
}

template<class T> string to_string(T n)
{
    ostringstream oss;
    oss<<n;
    oss.flush();
    return oss.str();
}
int to_int(string s)
{
    int r=0;
    istringstream sin(s);
    sin>>r;
    return r;
}

template<class T1> void put(T1 e)
{
    cout<<e<<endl;
}
template<class T1,class T2> void put(T1 e1,T2 e2)
{
    cout<<e1<<" "<<e2<<endl;
}
template<class T1,class T2,class T3> void put(T1 e1,T2 e2,T3 e3)
{
    cout<<e1<<" "<<e2<<" "<<e3<<endl;
}
template<class T1,class T2,class T3,class T4> void put(T1 e1,T2 e2,T3 e3,T4 e4)
{
    cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
}
template<class T1,class T2,class T3,class T4,class T5> void put(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
{
    cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
}
template<class T1> void putv(vector<T1>e1)
{
    for(int i=0; i<sz(e1); i++)(!i?cout<<e1[i]:cout<<" "<<e1[i]);
    cout<<endl;
}
template<class T1> void puta(T1 arr[],int l)
{
    for(int i=0; i<l; i++)(!i?cout<<arr[i]:cout<<" "<<arr[i]);
    cout<<endl;
}
template<class T1> bool tk(T1 &e1)
{
    return(cin>>e1?true:false);
}
template<class T1,class T2> bool tk(T1 &e1,T2 &e2)
{
    return(cin>>e1>>e2?true:false);
}
template<class T1,class T2,class T3> bool tk(T1 &e1,T2 &e2,T3 &e3)
{
    return(cin>>e1>>e2>>e3?true:false);
}
template<class T1,class T2,class T3,class T4> bool tk(T1 &e1,T2 &e2,T3 &e3,T4 &e4)
{
    return(cin>>e1>>e2>>e3>>e4?true:false);
}

int n,j,q,t,b,e,r,limit,k;
int cost[115],weight[10110],dp[115][10110];

int func( int i , int w )
{
    if( i==n+1 )return 0;
    if( dp[i][w]!=-1 )return dp[i][w];
    int p1=0,p2=0;
    //if( w+weight[i]<=k || ( w+weight[i]>2000 && w+weight[i]<=k+200 ) )
        p1=cost[i]+func( i+1,w+weight[i] );
    //pf("%d\n",w);
    p2=func( i+1,w );
    dp[i][w]=max( p1,p2 );
    //pf("%d\n",w);
    return dp[i][w];
}

int main()
{

//freopen("in.txt","r",stdin );
//freopen("out.txt","w",stdout );

    while(~sf("%d %d",&k,&n) )
    {
        r=0;
        int sum=0;
        memset( dp,-1,sizeof(dp) );
        for( j=1; j<=n; j++ )
        {
            sf("%d %d",&weight[j],&cost[j]);
        }
        r=func( 1,0 );
        sum+=r;
        pf("%d\n",sum);
    }

    return 0;
}

[Jujuedv]

Is it possible the uDebug code is incorrect?

For

Code: Select all

1803 2
2000 5
2 1

my AC solution gives

Code: Select all

6

but uDebug gives me

Code: Select all

1

this seems weird, since we can buy both for 2002$, get our 200$ refund and so we have only paid 1802$...

interestingly if i change it to the following it gives the correct answer of 6:

Code: Select all

1803 2
2001 5
2 1

[ebb]

Some information that may be relevant for anyone working on this problem: my code passed even though it returned different results for the test input of Morass in uDebug.

Concretely the following lines differed:
Line 494 -> uDebug 53, Mine 52
Line 548 -> uDebug 34, Mine 33
Line 549 -> uDebug 32, Mine 31
Line 646 -> uDebug 51, Mine 50

[lighted]

Now for Jujuedv's test case uDebug gives correct answer 6.

Some information that may be relevant for anyone working on this problem: my code passed even though it returned different results for the test input of Morass in uDebug.

Concretely the following lines differed:
Line 494 -> uDebug 53, Mine 52
Line 548 -> uDebug 34, Mine 33
Line 549 -> uDebug 32, Mine 31
Line 646 -> uDebug 51, Mine 50

Input (494, 548, 549, 646th test cases)

Code: Select all

1978 32
178 4
352 3
178 1
337 3
326 5
275 3
172 3
357 5
328 3
298 1
198 3
160 5
343 4
249 1
215 5
321 3
102 5
189 3
102 1
111 5
235 1
179 5
199 5
268 1
199 1
182 2
223 5
348 2
148 3
255 4
226 4
286 5

1847 20
380 4
157 4
262 3
321 3
325 1
196 1
154 5
315 5
106 1
337 5
314 5
341 4
297 3
149 3
196 2
232 2
147 1
258 3
103 1
203 1

1906 16
134 3
105 3
176 1
396 4
391 2
255 3
260 2
338 4
179 4
141 2
393 3
325 1
119 5
247 1
388 2
166 2

1886 37
302 3
242 1
129 4
213 3
151 4
352 3
158 1
300 3
264 3
150 2
377 3
310 4
382 3
369 1
152 3
389 1
358 2
202 4
187 4
182 5
213 4
385 1
222 2
210 5
313 3
102 3
396 2
344 3
351 2
242 2
292 5
258 5
107 4
328 5
136 2
107 4
178 5

My acc solution gives sames results as uDebug.

Here is optimal way for 548th test case. Total price is 2025 (200$ is refund), total favour value is 34.

Code: Select all

258 3
149 3
341 4
314 5
337 5
315 5
154 5
157 4