Cod sursa(job #3130009)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 16 mai 2023 16:41:45
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 50005;

int S[MAXN];
int mn[MAXN], pos[MAXN];

int main() {
  int n, k, x;

  fin >> n >> k;
  for ( int i = 1; i <= n; ++i ) {
	fin >> x;
	S[i] = S[i-1] + x;
	mn[i] = S[i];
  }
  pos[0] = 0;
  mn[0] = 0;
  for ( int i = 1; i <= n; ++i ) {
	if ( mn[i] > mn[i-1] ) {
	  mn[i] = mn[i-1];
	  pos[i] = pos[i-1];
	} else {
	  pos[i] = i;
	}
  }
  int res = -2e9, l = 0, r = 0;
  for ( int i = k; i <= n; ++i ) {
	if ( S[i] - mn[i - k] > res ) {
	  l = pos[i - k] + 1;
	  r = i;
	  res = S[i] - mn[i - k];
	}
  }
  fout << l << " " << r << " " << res;
  fin.close();
  fout.close();
  return 0;
}