Cod sursa(job #2677332)

Utilizator andrei102Pavel Andrei andrei102 Data 26 noiembrie 2020 11:41:21
Problema Secventa 2 Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>
int maxim(int a, int b)
{
    if(a<b)
        return b;
    return a;
}
void maximumSubarray(int n,int *arr,int *sol,int k,FILE *pf1)
{

    if(k == n)
    {
        fprintf(pf1,"1 %d %d",n,sol[n]);
        return;
    }
    int min = sol[1];
    sol[k+1] = maxim(sol[k+1],sol[k+1]-min);
    for(int i=k+2; i<=n; i++)
    {
        if(min>sol[i-k])
            min = sol[i-k];
        sol[i] = maxim(sol[i],sol[i]-min);
    }
    int max = sol[k];
    int i_right = k;
    for(int i=2; i<=n; i++)
    {
        if(max<sol[i])
        {
            max = sol[i];
            i_right = i;
        }
    }
    int i_left = 1;
    int minim = sol[i_left];
    for(int i=2; i<=i_right-k; i++)
    {
        if(minim>sol[i])
        {
            minim = sol[i];
            i_left = i;
        }
    }

    if(i_left == 1 && sol[1]<=sol[2])
        fprintf(pf1,"1 %d %d",i_right,max);
    else
        fprintf(pf1,"%d %d %d",i_left+1,i_right,max);
    fclose(pf1);
}
int main()
{
    FILE *pf1 = fopen("secv2.in","r+");
    FILE *pf2 = fopen("secv2.out","r+");
    if(pf1!=NULL && pf2!=NULL)
    {
        int n,k;
        fscanf(pf1,"%d%d",&n,&k);
        int arr[50001];
        int sol[50001];
        int sum = 0;
        for(int i=1; i<=n; i++)
        {
            fscanf(pf1,"%d",&arr[i]);
            sum+=arr[i];
            sol[i] = sum;

        }
        maximumSubarray(n,arr,sol,k,pf2);
        fclose(pf1);
        fclose(pf2);
    }

    return 0;
}