Cod sursa(job #789880)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 19 septembrie 2012 18:19:59
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

ifstream fi("secv2.in");
ofstream fo("secv2.out");

int N, K, *V;
int a, b, c = -(1 << 30);

void possible(int li, int ls, int sum)
{
  if(sum > c)
    a = li, b = ls, c = sum;
}

void write()
{
  fo << a + 2 << " "
     << b + 1 << " "
     << c << endl;
}

void read()
{
  fi >> N >> K;
  V = new int[N];
  int s = 0;
  for(int i = 0; i < N; i++)
  {
    fi >> V[i];
    s += V[i];
  }
}

void naive()
{
  for(int i = 0; i < N; i++)
  {
    for(int j = i + K - 1; j < N; j++)
    {
      int s = 0;
      for(int k = i; k <= j; k++)
        s += V[k];
      possible(i, j, s);
    }
  }
}

void print(int *v, int n)
{
  for(int i = 0; i < n; i++)
    cout << v[i] << " ";
  cout << endl;
}

int *KS;
void ksums()
{
  KS = new int[N];
  int s(0);
  for(int i = 0; i < N; i++)
  {
    s += V[i];
    KS[i] = s;
  }
}

void update_mpm(int& m, int& pm, int newp)
{
  if(KS[newp] < m)
  {
    m = KS[newp];
    pm = newp;
  }
}

void solve()
{
  int m = 0;
  int pm = -1;
  for(int i = K - 1; i < N; i++)
  {
    possible(pm, i, KS[i] - m);
//    cout << "C(" << i << ") = " << KS[i] - m << endl;
    update_mpm(m, pm, i - K + 1);
  }
}

void printbest()
{
  cout << "BEST: "
       << a + 1 << " "
       << b + 1 << " "
       << c << endl;
}

int main(int argc, char *argv[])
{
  read();
  ksums();
//  print(KS, N);
//  naive();
  solve();
  write();
  return 0;
}