Cod sursa(job #1599325)

Utilizator andreey_047Andrei Maxim andreey_047 Data 13 februarie 2016 19:29:01
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int nmax = 50008;

int N,K,a[nmax],sum[nmax],best,p1,p2;

struct el{
 int poz,x;
}st[nmax],dr[nmax];

inline void Precalc(){
 int i,s = 0,j = 1;

  for(i = 1; i <= N; ++i){
     s+=a[i];
     if(s < 0){
        s = 0;
        j = i+1;
        st[i].poz = i;
        st[i].x = a[i];
     }
     else{
        st[i].x = s;
        st[i].poz = j;
     }
  }
   s = 0;
   for(i = N; i; --i){
     s+=a[i];
     if(s < 0){
        s = 0;
        j = i-1;
        dr[i].poz = i;
        dr[i].x = a[i];
     }
     else{
        dr[i].x = s;
        dr[i].poz = j;
     }
  }
}

inline void Zoso(){
 int i,sf,l,r;
 best = -INF;
 for(i = K; i <= N; ++i){
     l = i-K+1; r = i;
     sf = sum[i]-sum[i-K];
        if(st[i-K].x>0)
    sf+=st[i-K].x,l = st[i-K].poz;
    if(dr[i+1].x>0)
    sf+=dr[i+1].x,r = dr[i+1].poz;

    if(sf > best){
        best = sf;
        p1 = l;
        p2 = r;
    }
 }
}

int main(){
    int i;
    freopen ("secv2.in","r",stdin);
    freopen ("secv2.out","w",stdout);
    scanf("%d %d\n",&N,&K);
    for(i = 1; i <= N; ++i){
        scanf("%d ",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    Precalc();
    Zoso();
    if(!p1)++p1;
    if(!p2)p2=N;

    printf("%d %d %d\n",p1,p2,best);
    return 0;
}