Maximum number of people that can be killed with strength P | C ++ implementation of the approach ; Function to return the maximum number of people that can be killed ; Storing the sum beforehand so that it can be used in each query ; lower_bound returns an iterator pointing to the first element greater than or equal to your val ; Previous value ; Returns the index in array upto which killing is possible with strength P ; Driver code
#include <algorithm> NEW_LINE #include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE static constexpr int kN = 1000000 ; int maxPeople ( int p ) { ll sums [ kN ] ; sums [ 0 ] = 0 ; for ( int i = 1 ; i < kN ; i ++ ) sums [ i ] = ( ll ) ( i * i ) + sums [ i - 1 ] ; auto it = std :: lower_bound ( sums , sums + kN , p ) ; if ( * it > p ) { -- it ; } return ( it - sums ) ; } int main ( ) { int p = 14 ; cout << maxPeople ( p ) ; return 0 ; }