Cod sursa(job #2059301)

Utilizator mihai.alphamihai craciun mihai.alpha Data 6 noiembrie 2017 21:01:07
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e4 + 5;

int n, l, u;
int cost[MAXN];
int timp[MAXN];
int sumc[MAXN], sumt[MAXN];

deque <int> q;

double maxi(double a, double b)  {
    if(a < b)
        return b;
    return a;
}

int main()  {
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    cin >> n >> l >> u;
    for(int i = 1;i <= n;i++)
        cin >> cost[i], sumc[i] = sumc[i - 1] + cost[i];
    for(int i = 1;i <= n;i++)
        cin >> timp[i], sumt[i] = sumt[i - 1] + timp[i];
    double ans = 1.0 * cost[l] / timp[l];
    for(int i = l;i <= n;i++)  {
        while(q.size() && q.front() <= i - u)
              q.pop_front();
        while(q.size() && 1LL * (sumc[i] - sumc[q.back()]) * (sumt[i] - sumt[i - l]) < 1LL * (sumc[i] - sumc[i - l]) * (sumt[i] - sumt[q.back()]))
              q.pop_back();
        q.push_back(i - l + 1);
        if(ans < 1.0 * (sumc[i] - sumc[q.front()]) / (sumt[i] - sumt[q.front()]))
            ans = 1.0 * (sumc[i] - sumc[q.front()]) / (sumt[i] - sumt[q.front()]);
    }
    cout << setprecision(2) << ans;
    return 0;
}