typedef long long ll;
ll solve( int * arr, int len) {
if ( len == 2 ) {
return ( arr[ 0 ] + arr[ 1 ] ) ;
}
else if ( len == 3 ) {
return max( max( arr[ 0 ] + arr[ 1 ] , arr[ 1 ] + arr[ 2 ] ) , 2 * ( arr[ 0 ] + arr[ 2 ] ) ) ;
}
else {
int half = len >> 1 ;
ll left_sol = solve( arr,half) ;
ll right_sol = solve( arr+ half, half + ( len% 2 ) ) ;
ll crossing_sol = - 1 ;
int indices_grow[ half] ;
int indices_decay[ half+ ( len% 2 ) ] ;
int maxi = - 1 ;
int count1 = - 1 ;
ll temp = 0 ;
for ( int i = 0 ; i < half; ++ i) {
if ( arr[ i] > maxi) {
indices_grow[ ++ count1] = i;
maxi = arr[ i] ;
}
}
int count2 = - 1 ;
maxi = - 1 ;
for ( int j = len- 1 ; j >= half; -- j) {
if ( arr[ j] > maxi) {
indices_decay[ ++ count2] = j;
maxi = arr[ j] ;
}
}
for ( int i = 0 ; i <= count1; ++ i) {
for ( int j = 0 ; j <= count2; ++ j) {
temp = ( arr[ indices_grow[ i] ] + arr[ indices_decay[ j] ] ) ;
temp = temp* ( indices_decay[ j] - indices_grow[ i] ) ;
if ( crossing_sol < temp) {
crossing_sol = temp;
}
}
}
return max( max( left_sol, right_sol) , crossing_sol) ;
}
}
dHlwZWRlZiBsb25nIGxvbmcgbGw7CmxsIHNvbHZlKGludCAqYXJyLCBpbnQgbGVuKXsKICAgIGlmIChsZW4gPT0gMil7CiAgICAgICAgcmV0dXJuIChhcnJbMF0rYXJyWzFdKTsKICAgIH0KICAgIGVsc2UgaWYgKGxlbiA9PSAzKXsKICAgICAgICByZXR1cm4gbWF4KG1heChhcnJbMF0rYXJyWzFdLCBhcnJbMV0rYXJyWzJdKSwgMiooYXJyWzBdK2FyclsyXSkpOwogICAgfQogICAgZWxzZSB7CiAgICAgICAgaW50IGhhbGYgPSBsZW4gPj4gMTsKICAgICAgICBsbCBsZWZ0X3NvbCA9IHNvbHZlKGFycixoYWxmKTsKICAgICAgICBsbCByaWdodF9zb2wgPSBzb2x2ZShhcnIraGFsZiwgaGFsZiArIChsZW4lMikpOwogICAgICAgIGxsIGNyb3NzaW5nX3NvbCA9IC0xOwogICAgICAgIGludCBpbmRpY2VzX2dyb3dbaGFsZl07CiAgICAgICAgaW50IGluZGljZXNfZGVjYXlbaGFsZisobGVuJTIpXTsKICAgICAgICBpbnQgbWF4aSA9IC0xOwogICAgICAgIGludCBjb3VudDEgPSAtMTsKICAgICAgICBsbCB0ZW1wID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGhhbGY7ICsraSl7CiAgICAgICAgICAgIGlmIChhcnJbaV0gPiBtYXhpKXsKICAgICAgICAgICAgICAgIGluZGljZXNfZ3Jvd1srK2NvdW50MV0gPSBpOwogICAgICAgICAgICAgICAgbWF4aSA9IGFycltpXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpbnQgY291bnQyID0gLTE7CiAgICAgICAgbWF4aSA9IC0xOwogICAgICAgIGZvciAoaW50IGogPSBsZW4tMTsgaiA+PSBoYWxmOyAtLWopewogICAgICAgICAgICBpZiAoYXJyW2pdID4gbWF4aSl7CiAgICAgICAgICAgICAgICBpbmRpY2VzX2RlY2F5WysrY291bnQyXSA9IGo7CiAgICAgICAgICAgICAgICBtYXhpID0gYXJyW2pdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPTA7IGkgPD0gY291bnQxOyArK2kpewogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8PSBjb3VudDI7ICsrail7CiAgICAgICAgICAgICAgICB0ZW1wID0gKGFycltpbmRpY2VzX2dyb3dbaV1dICsgYXJyW2luZGljZXNfZGVjYXlbal1dKTsKICAgICAgICAgICAgICAgIHRlbXAgPXRlbXAqKGluZGljZXNfZGVjYXlbal0gLSBpbmRpY2VzX2dyb3dbaV0pOwogICAgICAgICAgICAgICAgaWYgKGNyb3NzaW5nX3NvbCA8IHRlbXApewogICAgICAgICAgICAgICAgICAgIGNyb3NzaW5nX3NvbCA9IHRlbXA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHJldHVybiBtYXgobWF4KGxlZnRfc29sLCByaWdodF9zb2wpLCBjcm9zc2luZ19zb2wpOwoKICAgIH0KfQ==
compilation info
prog.cpp: In function ‘ll solve(int*, int)’:
prog.cpp:7:20: error: ‘max’ was not declared in this scope
return max(max(arr[0]+arr[1], arr[1]+arr[2]), 2*(arr[0]+arr[2]));
^~~
prog.cpp:7:16: error: ‘max’ was not declared in this scope
return max(max(arr[0]+arr[1], arr[1]+arr[2]), 2*(arr[0]+arr[2]));
^~~
prog.cpp:43:20: error: ‘max’ was not declared in this scope
return max(max(left_sol, right_sol), crossing_sol);
^~~
prog.cpp:43:20: note: suggested alternative: ‘maxi’
return max(max(left_sol, right_sol), crossing_sol);
^~~
maxi
prog.cpp:43:16: error: ‘max’ was not declared in this scope
return max(max(left_sol, right_sol), crossing_sol);
^~~
prog.cpp:43:16: note: suggested alternative: ‘maxi’
return max(max(left_sol, right_sol), crossing_sol);
^~~
maxi
stdout