Cod sursa(job #1807439)

Utilizator tanasaradutanasaradu tanasaradu Data 16 noiembrie 2016 16:42:55
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <bits/stdc++.h>
using namespace std;
int cost[30005],timp[30005],n,U,L,sol[30005],sol1[30005];
deque<int>maxim;
deque<int>minim;
ifstream fin ("secv3.in");
ofstream fout("secv3.out");
void Citire()
{
    int i;
    fin>>n>>U>>L;
    for(i=1;i<=n;i++)
        fin>>cost[i];
    for(i=1;i<=n;i++)
        fin>>timp[i];
    fin.close();
}
void Rezolvare()
{
    int x,i,t=0,t1=0;
    for(i=1;i<=n;i++)
        sol[t++]=cost[i];
     for(i=1;i<=n;i++)
        sol1[t1++]=timp[i];
    for(i=1;i<=n;i++)
    {
        cost[i]=cost[i-1]+cost[i];
        timp[i]=timp[i-1]+timp[i];
    }
    for(i=1;i<=n;i++)
    {
        x=cost[i];
        while(!maxim.empty() and cost[maxim.back()]<x)
            maxim.pop_back();
        while(!minim.empty() and cost[minim.back()]>x)
            minim.pop_back();
        maxim.push_back(i);
        minim.push_back(i);
        if(maxim.front()>minim.front())
        {
            if(maxim.front()-minim.front()>L)
                minim.pop_front();
        }
       else if(minim.front()-maxim.front()<U)
                maxim.pop_front();
        if(maxim.front()-minim.front()>=U and maxim.front()-minim.front()<=L)
            sol[++t]=cost[maxim.front()]-cost[minim.front()];
    }
    while(!maxim.empty())
        maxim.pop_front();
    while(!minim.front())
        minim.pop_front();
    for(i=1;i<=n;i++)
    {
        x=timp[i];
        while(!maxim.empty() and timp[maxim.back()]<x)
            maxim.pop_back();
        while(!minim.empty() and timp[minim.back()]>x)
            minim.pop_back();
        maxim.push_back(i);
        minim.push_back(i);
         if(maxim.front()>minim.front())
        {
            if(maxim.front()-minim.front()>L)
                minim.pop_front();
        }
        else
            if(minim.front()-maxim.front()<U)
                maxim.pop_front();
         if(maxim.front()-minim.front()>=U and maxim.front()-minim.front()<=L)
            sol1[++t1]=timp[maxim.front()]-timp[minim.front()];
    }
    double rez=-10000000;
    for(i=1;i<=t;i++)
        rez=max(rez,(double)sol[i]/sol1[i]);
    fout<<fixed<<setprecision(2)<<rez<<"\n";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}