Cod sursa(job #827756)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 2 decembrie 2012 17:01:20
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_SIZE 100002
using namespace std;

long deque[MAX_SIZE] , sume[MAX_SIZE];

int main()
{
    FILE *input = fopen("secv2.in","r");
    FILE *output = fopen("secv2.out","w");

    int n;
    int l;
    int u;

    fscanf(input,"%d%d",&n,&l);
    u = n;
    for (int i=0;i<n;i++)
    {
        int x;
        fscanf(input,"%d",&x);
        if (i ==0) sume[i] = x;
        else sume[i] = sume[i-1] + x;
    }
    int start = 0;
    int end = 0;
    deque[start] = 0;
    long maxim = -MAX_SIZE;
    int start_poz;
    int end_poz;
    for (int i=1;i<n;i++)
    {
        if (i - deque[start] > u)
        {
            start++;
        }
        while ( sume[deque[end]] > sume[i] && start <= end)
        {
            end--;
        }
        end++;
        deque[end] = i;
        if (sume[i] - sume[deque[start]] > maxim && i >= deque[start] + l)
        {
            maxim = sume[i] - sume[deque[start]];
            start_poz = deque[start]+1;
            end_poz = i;
        }
    }
    fprintf(output,"%d %d %ld",start_poz+1,end_poz+1,maxim);
    fclose(input);
    fclose(output);
    return 0;
}