Cod sursa(job #1730999)

Utilizator mircea_marian.popaPopa Mircea-Marian mircea_marian.popa Data 18 iulie 2016 00:22:58
Problema Secventa 3 Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
unsigned short l, u;

unsigned char hasPosSubArr(unsigned short n, unsigned short data[2][n],
        double cat){
    double diff[n];
    unsigned short i;
    double sum = 0;
    l--;
    for( i  = 0 ; i < l ; i++ ){
        diff[i] = data[0][i]-cat*data[1][i];
        sum += diff[i];
    }
    for( i = l ; i < n ; i++ )
        diff[i] = data[0][i]-cat*data[1][i];
    l++;

    unsigned short st = 0 , dr = l - 2 , dim = l - 1;
    for( i = l - 1 ; i < n ; i++ ){
        if( sum + diff[i] >= 0 )
            return 1;
        sum += diff[i];
        dim ++;
        dr ++;
        if(dim > u ){
            sum -= diff[st];
            st ++;
            dim --;
        }
        while( diff[st] <= 0 && dim >= l ){
            sum -= diff[st];
            st++;
            dim --;
        }
    }

    return 0;
}

void main(){
    FILE * fi = fopen("secv3.in","rt");
    unsigned short n, i;
    fscanf( fi , "%hd %hd %hd\n" , &n , &l , &u );
    unsigned short data[2][n];
    n--;
    for(i = 0 ; i < n ; i++ )
        fscanf( fi , "%hd " , &data[0][i] );
    fscanf( fi , "%hd\n" , &data[0][n] );
    for(i = 0 ; i < n ; i++ )
        fscanf( fi , "%hd " , &data[1][i] );
    fscanf( fi , "%hd" , &data[1][n] );
    n++;
    //for(i = 0 ; i < n ; i++ )
        //printf( "%hd " , data[1][i] );
    fclose(fi);
    clock_t t = clock();
    double ans = 0, j;
    //unsigned short k = 0;
    for( j = 1 << 9 ; j > 0.001 ; j /= 2 ){
        if( hasPosSubArr( n, data, j + ans ) )
            ans+=j;
        //k++;
    }

    fi = fopen("secv3.out","wt");
    //fprintf(fi,"%.2f %d\n", ans, k);
    fprintf(fi,"%.2f\n", ans);
    fclose(fi);
    //printf("time=%f\n",( (float)clock() - t ) / CLOCKS_PER_SEC );
}