public class FoxAndSouvenirTheNext
{
public String ableToSplit
( int [ ] value
) {
boolean [ ] [ ] ableToGet = new boolean [ 51 ] [ 2501 ] ;
for ( int i = 0 ; i < value.length ; i++ )
for ( int j = 0 ; j <= 2500 ; j++ )
ableToGet[ i] [ j] = false ;
ableToGet[ 0 ] [ 0 ] = true ;
int sum = 0 ;
for ( int i = 0 ; i < value.length ; i++ )
{
sum += value[ i] ;
for ( int j = i; j >= 1 ; j-- )
for ( int k = 2500 ; k >= value[ i] ; k-- )
ableToGet[ j] [ k] |= ableToGet[ j- 1 ] [ k - value[ i] ] ;
}
if ( value.length % 2 == 0 && sum % 2 == 0 && ableToGet[ value.length / 2 ] [ sum / 2 ] == true )
return "Possible" ;
return "Impossible" ;
}
}
cHVibGljIGNsYXNzIEZveEFuZFNvdXZlbmlyVGhlTmV4dAp7CgoJcHVibGljIFN0cmluZyBhYmxlVG9TcGxpdChpbnRbXSB2YWx1ZSkKCXsKCQlib29sZWFuW11bXSBhYmxlVG9HZXQgPSBuZXcgYm9vbGVhbls1MV1bMjUwMV07CgkJZm9yKGludCBpID0gMDsgaSA8IHZhbHVlLmxlbmd0aDsgaSsrKQoJCQlmb3IoaW50IGogPSAwOyBqIDw9IDI1MDA7IGorKykKCQkJCQlhYmxlVG9HZXRbaV1bal0gPSBmYWxzZTsKCQlhYmxlVG9HZXRbMF1bMF0gPSB0cnVlOwoJCWludCBzdW0gPSAwOwoJCWZvcihpbnQgaSA9IDA7IGkgPCB2YWx1ZS5sZW5ndGg7IGkrKykKCQl7CgkJCXN1bSArPSB2YWx1ZVtpXTsKCQkJZm9yKGludCBqID0gaTsgaiA+PSAxOyBqLS0pCgkJCQlmb3IoaW50IGsgPSAyNTAwOyBrID49IHZhbHVlW2ldOyBrLS0pCgkJCQkJYWJsZVRvR2V0W2pdW2tdIHw9IGFibGVUb0dldFtqLTFdW2sgLSB2YWx1ZVtpXV07CgkJfQoJCWlmKHZhbHVlLmxlbmd0aCAlIDIgPT0gMCAmJiBzdW0gJSAyID09IDAgJiYgYWJsZVRvR2V0W3ZhbHVlLmxlbmd0aCAvIDJdW3N1bSAvIDJdID09IHRydWUpCgkJCXJldHVybiAiUG9zc2libGUiOwoJCXJldHVybiAiSW1wb3NzaWJsZSI7Cgl9Cgp9Cg==