Cod sursa(job #51622)

Utilizator cos_minBondane Cosmin cos_min Data 15 aprilie 2007 20:45:52
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
using namespace std;

#define in "secv2.in"
#define out "secv2.out"
#define dim 50001
#define infinit 1000000

int A[dim], Nr[dim];
long long best[dim], spart[dim];
int N, K;

int main()
{
    int is, ip;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    spart[0] = 0;
    
    scanf("%d%d", &N, &K);
    for ( int i = 1; i <= N; i++ )
        scanf("%d", &A[i]), spart[i] = spart[i-1] + A[i];
    
    Nr[0] = 0;
    best[0] = 0;
    
    for ( int i = 1; i <= N; i++ )
    {
        best[i] = A[i];
        Nr[i] = i;
        if ( best[i] <= A[i] + best[i-1] ) best[i] = A[i] + best[i-1], Nr[i] = Nr[i-1];
    }
    
    long long maxim = -infinit;
    
    for ( int i = 1; i <= N; i++ )
    {
       // printf("%d ", best[i] );
        if ( maxim < best[i] && i-Nr[i]+1 >= K ) maxim = best[i], ip = Nr[i], is = i;
    }
    
    if ( maxim == -infinit )
    {
         for ( int i = K; i <= N; i++ ) 
         {
             if ( maxim < spart[i] - spart[i-K-1] ) maxim = spart[i] - spart[i-K], ip = i-K+1, is = i;
         }
         
         printf("%d %d %d", ip, is, maxim);
    }
    else
    {
        printf("%d %d %d", ip, is, maxim);
    }
    
    return 0;
}