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
11782 - Optimal Cut
Moderator: Board moderators
Re: 11782
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
-
- Learning poster
- Posts: 96
- Joined: Tue Apr 23, 2013 12:54 pm
Re: 11782 - Optimal Cut
Getting WA
I have tested several i/o
all of them were correct
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;
}