11782 - Optimal Cut

[Gourav.in]

i have written a bottom up DP in tree for it .. but WA can any one just post some corner case for this question .

with regards,
Gourav

[Gourav.in]

here is my code . plzz point out the bug in it

Code: Select all

#include<iostream>
#include<stack>
#include<vector>
#include<cstdio>
using namespace std;
#define INF 1048576001
static int dp[( 1 << 20)][20];
static int N , a[ ( 1 << 20) ] , arr[ ( 1 << 20 ) ], K;
int main()
{
	while( 1 )
	{
		scanf("%d",&N);
		if( N == -1) break;
		scanf("%d",&K);
		int L = ((1 << N) << 1) -1;
		for(int i = 0; i < L; ++i)
		{
				scanf("%d",&a[i]);
		}
		vector< int > v;
		stack < int > s;
		s.push(0);
		//cout << ":)\n";
		while(!s.empty())
		{
			int x = s.top();
			s.pop();
			v.push_back(x);
			int l =(x+1)*2 -1;
			int r =(x+1)*2 ;
			if( r < L)
			{
			s.push(r);
			s.push(l);
			}
		}
		for(int i = 0; i < L; ++i)
			arr[v[i]] = a[i];
		for(int i = 0; i < L; ++i)
			dp[i][0] = arr[i];
		int F = 2;
		int mx = (1 << N);
		if( F > K) F =K;
		L =  (1 << N) - 1;
		N--;
		for(int i = L -1 ; i >= 0; --i)
		{
			//cout << arr[i] << " ";
			for( int j = 1; j < F; ++j)
			{
				dp[i][j]=-INF;
				for(int k = 0; k < j ;++k)
				{
				dp[i][j] = max( dp[i][j] , dp[(i+1)*2 - 1][k] + dp[(i+1)*2][j-k-1]);	
				}
			}
			if( i == (1 << N) -1) { F*=2; N--; }
			if( F > K) F=K;
		}
		int res = -INF;
		for(int i = 0; i < min(mx,K); ++i)
		{
			//cout << dp[0][i] << " ";
			res= max( dp[0][i] , res);
		}
		cout << res << "\n" ;
	}
	return 0;
}

[brianfry713]

This prints only 0 for the sample input.

[brianfry713]

Disregard my previous post. I wrote an AC solution using a bottom up DP tree.

Try this input:
3 7 283 -677 63 813 -970 746 526 973 83 118 -283 -970 -540 158 -699

The output should be 1645.

[Repon kumar Roy]

Getting WA
I have tested several i/o
all of them were correct

Code: Select all

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

/*------- Constants---- */
#define LMT				2100000
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF                      63
#define MEM_VAL                         1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)                         make_pair(i,j)
#define lop(i,a,b)                      for( int i = (a) ; i < (b) ; i++)
#define pb(a)                           push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<25
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)                        cout <<#x <<" -> " << x << endl;
#define EPS				1e-7
#define fred()                          freopen("in.txt","r",stdin);
#define fwrt()                          freopen("in.txt","w",stdout);
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

int H , K ;
int cnt = 0;
int Values[LMT];
int iAr[LMT];
int DP[LMT][22];

void PreOrder(int n , int h )
{
        if( h > H ) return;
        Values[n] = iAr[cnt ++];
        PreOrder(2 * n , h + 1 );
        PreOrder(2 * n + 1 , h + 1) ;
}

int Trv(int u , int k , int h )
{
        
        if( h > H ) return -inf ;
        DP[u][1] = Values[u];
        if( DP[u][k] !=-1 ) return DP[u][k];
        
        int r = -inf;
        for( int j = 1; j < k ; j ++ ) {
                r = max( r , Trv(2* u , j , h + 1) + Trv(2 * u + 1, k - j , h + 1)) ;
        }
        return DP[u][k] = r;
        
}
int main()
{
        
        while( scanf("%d" , &H) == 1) {
                if(H == -1 ) break;
                scanf("%d",&K);
                int T = (1 << (H+1)) - 1;
                for( int i = 0; i < T ; i ++ ) {
                        ms(DP[i+1], -1);
                        sc(iAr[i]);
                }
                cnt = 0;
                PreOrder(1 , 0 );
                int ans = - inf;
                for(int i = 1; i <= K ; i ++ ) {
                        ans = max ( ans , Trv(1 , i , 0));
                }
                
                printf("%d\n" ,ans );
        }
        return 0;
}