Cod sursa(job #985224)

Utilizator danlexDan Alexandru danlex Data 16 august 2013 22:50:12
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define MAX  500002
#define INF 1250000001

int u, l, n, t[MAX], c[MAX], xmin, xmax, dqsum = -INF;
deque<int> dq;
long long xsum = -INF, sumt[MAX], sumc[MAX];

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 << xmin << " " << xmax << " " << xsum/100 << ".";
	if(xsum%100 >= 10){
		cout << xsum % 100;
	} else {
		cout << "0" << xsum % 100;
	}
	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 << xsum / 100 << ".";
	if(xsum%100 >= 10){
        fo << xsum % 100;
    } else {
        fo << "0" << xsum % 100;
    }	
    fo.close();
}

void compute(){
	sumc[0] = 0;
	for(int i = 1; i <= n; i++){
        sumc[i] = sumc[i-1] + c[i];
    }

	sumt[0] = 0;
    for(int i = 1; i <= n; i++){
        sumt[i] = sumt[i-1] + t[i];
    }

	int i = 1;
    while(i <= n){
		dq.push_back(i);
        if(!dq.empty() && (dq.back() - dq.front() >= l - 1) 
			&& (dq.back() - dq.front() <= u - 1)){
			dqsum = (sumc[i] - sumc[i - l]) * 100 / (sumt[i] - sumt[i - l]);
			if(dqsum > xsum){
				xsum = dqsum;
				xmin = dq.front();
				xmax = dq.back();
			}
        }
		if(!dq.empty() && (dq.back() - dq.front() == u - 1)){
            dq.pop_front();
            i = dq.front();
            if(!dq.empty() && (dq.back() - dq.front() >= l - 1)
                && (dq.back() - dq.front() <= u - 1)){
                dqsum = (sumc[i] - sumc[i - l]) * 100 / (sumt[i] - sumt[i - l]);
                if(dqsum > xsum){
                    xsum = dqsum;
                    xmin = dq.front();
                    xmax = dq.back();
               }
            }
        }
		i ++;
    }
}
int main(void){
    read();
    compute();
	//print();
	write();
    return 0;
}