Cod sursa(job #217718)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 29 octombrie 2008 22:38:21
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define inf 0x3f3f3f

using namespace std;

ifstream fin ("secv2.in");
ofstream fout ("secv2.out");

int sir[50010],suma[50010],n,poz[50010];
int k;

void citire()
{
     fin>>n>>k;
     for (int i=0;i<n;i++)
          fin>>sir[i];
}

int main ()
{
     citire();
     int S=0,p=n-1;
     poz[n]=n-1;
     for (int i=n-1;i>=0;i--)
     {
          S+=sir[i];
          if (S<=0)
          {
               p=i-1;
               S=0;
          }
          poz[i]=p;
          suma[i]=S;
     }
     int MAX=-inf,I=0,F,S_aux=0;
     for (int i=0;i<k;i++)
          S_aux+=sir[i];
     MAX=S_aux+suma[k];
     I=0;
     F=poz[k];
     for (int i=k;i<n;i++)
     {
          S_aux-=sir[i-k];
          S_aux+=sir[i];
          if (S_aux+suma[i+1]>MAX)
          {
               MAX=S_aux+suma[i+1];
               I=i-k+1;
               F=poz[i+1];
          }
     }
     fout<<I+1<<" "<<F+1<<" "<<MAX;
     return 0;
}