Cod sursa(job #993043)

Utilizator danlexDan Alexandru danlex Data 3 septembrie 2013 08:41:32
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <deque>
using namespace std;
#define MAX  500002
#define INF 1250000001

int u, l, n, t[MAX], c[MAX];
long long sumt[MAX], sumc[MAX];
double xsum;

void print(){
	cout << endl;
	cout << n << " " << l << " " << u << endl;
	for(int i = 1; i <= n; i ++){
		cout << c[i] << " ";
	}
	cout << endl;
	for(int i = 1; i <= n; i ++){
		cout << t[i] << " ";
	}
	cout << endl;
	cout << setprecision(2) << xsum ;
	cout << endl;
}

void read(){
	ifstream fi("secv3.in");
	fi >> n >> l >> u;
    for(int i = 1; i <= n; i++){
    	fi >> c[i];
	}
    for(int i = 1; i <= n; i++){
		fi >> t[i];
	}
	fi.close();
}

void write(){
    ofstream fo("secv3.out");
    fo << setprecision(2) << xsum;
    fo.close();
}

double dqsum(int first, int last){
 	double ret  = (double)(sumc[last] - sumc[first]) / (double)(sumt[last] - sumt[first]);
	return ret;
}

void compute(){
	int i;
	deque<int> dq;
	sumc[0] = 0, sumt[0] = 0;
	for (int i = 1; i <= n; i++){
        sumc[i] = sumc[i-1] + c[i];
		sumt[i] = sumt[i-1] + t[i];
    }

	for (i = l; i <= n; i ++){
		if(!dq.empty()){
			xsum = max(xsum, dqsum(dq.front(), i));
			xsum = max(xsum, dqsum(dq.front(), i - 1));
		}
		
		dq.push_back(i - l);
		
		if(!dq.empty() && dq.front() + u == i){
			dq.pop_front();
		}
	}

	while(!dq.empty()){
        xsum = max(xsum, dqsum(dq.front(), i));
		xsum = max(xsum, dqsum(dq.front(), i - 1));
		dq.pop_front();
    }
}
int main(void){
    read();
    compute();
	//print();
	write();
    return 0;
}