Cod sursa(job #2821127)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 decembrie 2021 10:15:13
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
   
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
    
static inline int min( int a, int b ) {
    return ( a <= b ? a : b );
}
 
static inline int max( int a, int b ) {
    return ( a >= b ? a : b );
}
 
static inline int mod( int x ) {
    return x < 0 ? -x : x;
}

#define MAX 50000
  
int S[ MAX + 1 ];
int sum[ MAX +  1 ];
int n, s, k;

int main()
{
    FILE *fin = fopen( "secv2.in", "r" );
    fscanf( fin, "%d%d", &n, &k );

    int x;
    for( int i = 1; i <= n; i++ ) {
        fscanf( fin, "%d", &x );
        s = max( s + x, 0 );
        sum[ i ] = s;
        S[ i ] = S[ i - 1 ] + x;
    }

    int maxx = S[ k ], left = 1, right = k;
    for( int i = k + 1; i <= n; i++ ) {
        if( maxx < S[ i ] - S[ i - k ] + sum[ i - k ] ) {
            maxx = S[ i ] - S[ i - k ] + sum[ i - k ];
            right = i;
        }
    }

    FILE *fout = fopen( "secv2.out", "w" );
    int sum = S[ right ] - S[ right - k ];
    left = right - k;
    while( ( sum += S[ left ] - S[ left - 1 ] ) != maxx )
        --left;
    fprintf( fout, "%d %d %d\n", max( 1, left ), right, maxx );
    fclose( fin );
    return 0;
}