Cod sursa(job #787126)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 12 septembrie 2012 17:37:38
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <fstream>
#include <algorithm>

using namespace std;

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

FILE *fileread, *fout;
int n, l,u;
int pos, posEnd;
double maxNo;

int cost[MAX];
int timp[MAX];

void process(){
	int i;
	double sumScore;

	maxNo = 0;

	double costSum = 0;
	double costTimp = 0;

	// compute the sum of the first L elements
	for(i=0; i<l; i++){
		costSum = costSum + cost[i];
		costTimp = costTimp + timp[i];
	}

	maxNo = sumScore = (1.*costSum/costTimp) ;
	double bestCost = costSum;
	double bestTimp = costTimp;

	pos = 0;
	posEnd = l;
	int tmpEnd = l;
	int tmpStart = 0;

	for(i = l ; i< n ; i++){
		costSum = costSum + cost[i] - cost[i-l];
		costTimp = costTimp + timp[i] - timp[i-l];
		sumScore =  costSum/costTimp;

		if(sumScore <  (bestCost + cost[i])/(bestTimp + timp[i])
				&& (tmpEnd <= u)){
			tmpEnd ++;
			bestCost = bestCost + cost[i];
			bestTimp = bestTimp + timp[i];
		}else{
			tmpEnd = l;
			tmpStart = i -l +1;
			bestCost = costSum;
			bestTimp = costTimp;
		}

		if ((maxNo <  bestCost/bestTimp ) && (tmpEnd <= u)){
			pos = tmpStart ;
			posEnd = tmpEnd;
			maxNo = 1*bestCost/bestTimp;

		}
	}

}

void output(){

	fout = fopen(outputFile, "w");
	fprintf(fout, "%f",
			maxNo);
	fclose(fout);
}


int main() {
	// read the file data
	ifstream in(inputFile);
	in>>n>>l>>u;
	for(int i = 0; i < n; i++) in>>cost[i];
	for(int i = 0; i < n; i++) in>>timp[i];

	// compute the max secv
	process();

	// output results
	output();

	return 0;
}