Cod sursa(job #2917551)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 5 august 2022 16:54:10
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#define L 50005
#define LL 2000000001
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int sp[L], mx[L], ri[L];
int main(){
  int n, k, i, smax, x, l, r;
  fin >> n >> k;
  for (i = 1; i <= n; i++){
    fin >> x;
    sp[i] = sp[i - 1] + x;
  }
  mx[n] = sp[n];
  ri[n] = n;
  for (i = n - 1; i >= 0; i--)
    if (mx[i + 1] > sp[i]){
      mx[i] = mx[i + 1];
      ri[i] = ri[i + 1];
    }
    else{
      mx[i] = sp[i];
      ri[i] = i;
    }
  smax = l = r = -LL;
  for (i = 1; i <= n; i++)
    if (i + k < n + 2 && smax < mx[i + k - 1] - sp[i - 1]){
      smax = mx[i + k - 1] - sp[i - 1];
      l = i;
      r = ri[i + k - 1];
    }
  fout << l << " " << r << " " << smax << "\n";
  return 0;
}