Pagini recente » Cod sursa (job #80696) | Cod sursa (job #555010) | Cod sursa (job #2612636) | Cod sursa (job #2927118) | Cod sursa (job #2455677)
#include <fstream>
using namespace std;
ifstream fin( "secv2.in" );
ofstream fout( "secv2.out" );
int N, K;
int a[50001];
int dp[50001];
void Read()
{
fin >> N >> K;
for( int i = 1; i <= N; ++i )
fin >> a[i];
fin.close();
}
void Do()
{
for( int i = 1; i <= N; ++i )
dp[i] = max( a[i], a[i] + dp[i - 1] );
int max_k, curent = 0, end_p;
for( int i = 1; i <= K; ++i )
curent += a[i];
max_k = curent;
end_p = K;
for( int i = K + 1; i <= N; ++i )
{
curent = curent + a[i] - a[i - K];
if( max( curent, curent + dp[i - K] ) > max_k )
{
max_k = max( curent, curent + dp[i - K] );
end_p = i;
}
}
int start_p, temp = 0;
for( int i = end_p; i > 0; --i )
{
temp += a[i];
if( temp == max_k ) start_p = i;
}
fout << start_p << ' ' << end_p << ' ' << max_k << '\n';
}
int main()
{
Read();
Do();
return 0;
}