Cod sursa(job #955809)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 1 iunie 2013 15:43:14
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <tuple>

std::tuple< int, int, int > max_subarray( const short* const p, const int size, const int k )
{
	int sum_max = -25001;
	int begin = 0, end = 0;
	int sum = 0;

	for ( int i = 0; i < size; i++ )
	{
		sum += p[ i ];
		if ( sum < 0 )
		{
			sum = 0;
			begin = i;
			if ( p[ i ] >= sum_max )
			{
				sum_max = p[ i ];
				begin = end = 1;
			}
		}
		else
		{
			if ( sum >= sum_max || end - begin + 1 < k )
			{
				sum_max = sum;
				end = i;
			}
		}
	}

	return std::make_tuple( begin, end, sum_max );
}

int main()
{
    std::ifstream cin("secv2.in");
    std::ofstream cout("secv2.out");

	int n = 0, k = 0;

	cin >> n >> k;

	short num[ 50000 ];

    int sum = 0;

	for ( int i = 0; i < n; i++ )
		cin >> num[ i ], sum += num[ i ];

	auto ans = max_subarray( num, n, k );

	int begin = std::get< 0 >( ans );
	int end = std::get< 1 >( ans );
	int sum_max = std::get< 2 >( ans );

    if ( n == k )
        cout << 1 << " " << n << " " << sum;
    else
        cout << begin + 1 << " " << end + 1 << " " << sum_max;
}