Cod sursa(job #787086)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 12 septembrie 2012 16:34:38
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
//============================================================================
// Name        : Coding.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <stdio.h>
#include <algorithm>

using namespace std;

#define inputFile  "secv2.in"
#define outputFile  "secv2.out"
#define MAX 500005

FILE *fileread, *fout;
int n, k;
int pos, posEnd, maxNo;

char numbers[MAX*10];
int secv[MAX];

void readFile(){
	int j=0, order;
	fileread = fopen(inputFile, "r");
	fscanf(fileread, "%d %d\n", &n, &k);
	fgets(numbers, sizeof(numbers), fileread);

	for(int i =0; i< n; i++){
		secv[i]=0;
		order = 0;

		while(numbers[j]!='-' &&
				(numbers[j]<'0' || numbers[j]> '9'))
			j++;

		if(numbers[j]=='-'){
			order = 1;
			j++;
		}
		while(numbers[j]>='0' && numbers[j]<='9'){
			secv[i]=secv[i]*10+(numbers[j]-'0');
			j++;
		}

		if(order)
			secv[i] =-secv[i];
	}

	fclose(fileread);
}

void process(){
	int i;
	int sum = 0, best;
	maxNo = 0;

	// compute the sum of the first L elements
	for(i=0; i<k; i++)
		sum = sum + secv[i];

	maxNo = best = sum ;
	pos = 0;
	posEnd = k;
	int tmpEnd = 0;
	int tmpStart = 0;

	for(i = k ; i< n ; i++){
		sum = sum + secv[i] - secv[i-k];

		if(sum < best + secv[i]){
			tmpEnd ++;
			best = best + secv[i];
		}else{
			tmpEnd = k;
			tmpStart = i -k +1;
			best = sum;
		}

		if (maxNo <  best){
			pos = tmpStart ;
			posEnd = tmpEnd;
			maxNo = best;
		}

	}

	pos = pos +1;
}

void output(){

	fout = fopen(outputFile, "w");
	fprintf(fout, "%d %d %d", pos,
			posEnd+pos-1,
			maxNo);
	fclose(fout);
}


int main() {
	// read the file
	readFile();

	// compute the max secv
	process();

	// output results
	output();

	return 0;
}