Cod sursa(job #368657)

Utilizator vladiiIonescu Vlad vladii Data 25 noiembrie 2009 12:22:40
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#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;
}