Cod sursa(job #943843)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 26 aprilie 2013 16:25:03
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<fstream>
#include<iostream>
#include<algorithm>

using namespace std;

int nums[50005], dpl[50005], dpr[50005], ml[50005], mr[50005];

int main(){
  ifstream in("secv2.in");
  ofstream out("secv2.out");

  int n, k;
  in >> n >> k;

  for(int i = 1; i <= n; ++i){
    in >> nums[i];
    dpl[i] = dpr[i] = nums[i];
    if(dpl[i - 1] > 0){
      ml[i] = ml[i - 1] + 1;
      dpl[i] += dpl[i - 1];
    }
    else
      ml[i] = 1;
  }

  for(int i = n; i > 0; --i)
    if(dpr[i + 1] > 0){
      mr[i] = mr[i + 1] + 1;
      dpr[i] += dpr[i + 1];
    }
    else
      mr[i] = 1;

  for(int i = 1; i <= n; ++i)
    nums[i] = nums[i] + nums[i - 1];

  int ans = -2e9, x, y;
  for(int i = k; i <= n; ++i){
    int lf = i - k + 1, rt = i, pans = nums[i] - nums[lf - 1];
    if(dpl[lf - 1] > 0){
      pans += dpl[lf - 1];
      lf -= ml[lf - 1];
    }
    if(dpr[i + 1] > 0){
      rt += mr[i + 1];
      pans += dpr[i + 1];
    }
    if(pans > ans){
      ans = pans;
      x = lf;
      y = rt;
    }
  }

  out << x << " " << y << " " << ans;

  return 0;
}