Pagini recente » Cod sursa (job #2178932) | Cod sursa (job #1766170) | Cod sursa (job #2420160) | Cod sursa (job #413943) | Cod sursa (job #368657)
Cod sursa(job #368657)
#include <iostream>
#include <fstream>
#include <deque>
//#include <conio.h>
using namespace std;
int n, l, u, c[30001], t[30001];
float binar(float x) {
float b[30001], sum[30001], mini, maxi;
int i;
deque<pair<float, int> > deq;
b[1]=c[1]-t[1]*x;
sum[1]=b[1];
for(i=2; i<=n; i++) {
b[i]=c[i]-t[i]*x;
sum[i]=sum[i-1]+b[i];
}
deq.push_back(make_pair(10000, 10000));
mini=10000; maxi=-100000;
for(i=1; i<=n; i++) {
//sum[i]-sum[j]
//pentru i-L > j >= i-U
//for(j=i-u; j<i-l; j++) {
//aflu minimul dintre sum[j]
//sterg daca <i-u
//adaug pe i-1-l
if(i-u<1 && i-l>=1) {
//cout<<i<<endl;
while(!deq.empty() && sum[i-l]<=deq.back().first) {
deq.pop_back();
}
deq.push_back(make_pair(sum[i-l], i-l));
if(mini>deq.front().first) {
mini=deq.front().first;
}
//cout<<i<<": "<<sum[i]<<" - "<<mini<<endl;
if(sum[i]-mini>maxi) {
maxi=sum[i]-mini;
}
}
else if(i-u>=1 && i-l>=1) {
if(deq.front().second<=i-u-1) { deq.pop_front(); }
while(!deq.empty() && sum[i-l]<=deq.back().first) {
deq.pop_back();
}
deq.push_back(make_pair(sum[i-l], i-l));
if(deq.front().first<mini) {
mini=deq.front().first;
}
//cout<<i<<": "<<sum[i]<<" - "<<mini<<endl;
if(sum[i]-mini>maxi) {
maxi=sum[i]-mini;
}
}
}
return maxi;
}
int main() {
fstream f1, f2;
int i, j, mij, val, st, dr;
float p, q;
f1.open("secv3.in", ios::in);
f1>>n>>l>>u;
for(i=1; i<=n; i++) {
f1>>c[i];
}
for(i=1; i<=n; i++) {
f1>>t[i];
}
f1.close();
//cautare binara
//p=binar(0.83);
st=-1000; dr=1000;
while(st<dr) {
mij=st+(dr-st)/2;
p=(float)mij/100;
q=binar(p);
if(-0.001<q && q<0.001) { break; }
else if(q<0) { dr=mij-1; }
else if(q>0) { st=mij+1; }
}
//end cautare binara
f2.open("secv3.out", ios::out);
f2<<p<<endl;
f2.close();
//getch();
return 0;
}