Ok, pai eu am rezolvat problema folosind heap-uri. Creez un max-heap si la fiecare pas extrag p maxime, scad minimul din toate si le reintroduc in heap. Iar numarul de siruri formate la fiecae pas p*min, apoi la final adun numaul de element ramase in heap. Problema este ca nu inteleg de ce pic pe al doilea test, daca puteti sa-mi spuneti unde gresesc ?
#include <fstream>
#include <iterator>
#define Nmax 100001
/*
*
*/
using namespace std;
int N;
int H[Nmax], v[Nmax];
void DownHeap( int k )
{
int son;
while( true )
{
son=2*k;
if( son > N )
return;
if( son < N && H[son] < H[son+1] )
++son;
if( H[k] >= H[son] )
return;
swap( H[k], H[son] );
k=son;
}
}
void UpHeap( int k )
{
int key=H[k], f=k/2;
while( k > 1 && key > H[f] )
{
swap( H[k], H[f] );
k=f;
f/=2;
}
}
int main( void )
{
int k, i, j;
ifstream in("sirag.in");
in>>N>>k;
copy( istream_iterator<int>( in ), istream_iterator<int>(), H+1 );
for( i=N/2; i > 0; --i )
DownHeap( i );
for( j=0; N >= k; j+=k*v[k] )
{
for( i=1; i <= k; ++i )
{
v[i]=H[1];
H[1]=H[N];
--N;
DownHeap( 1 );
}
for( i=1; i < k; ++i )
{
v[i]-=v[k];
if( v[i] > 0 )
{
H[++N]=v[i];
UpHeap( N );
}
}
}
j+=N;
ofstream out("sirag.out");
out<<j<<'\n';
return 0;
}