Cod sursa(job #2455677)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 12 septembrie 2019 12:49:40
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#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;
}