Cod sursa(job #2005385)

Utilizator richieYRichie Yeung richieY Data 26 iulie 2017 22:15:27
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");
int main() {
    int l, u, n;
    fin >> n >> l >> u;

    u = min(u, 2*l);

    vector<int> t(n);
    vector<int> b(n);
    vector<double> v(n);
    for (int i = 0; i < n; i += 1) {
        fin >> t[i];
    }
    
    for (int i = 0; i < n; i += 1) {
        fin >> b[i];
        v[i] = (double) 1.0*t[i]/b[i];
    }
    
    int tSum = 0;
    int bSum = 0;
    double ans = 0;
    for (int i = 0; i < l; i += 1) {
        tSum += t[i];
        bSum += b[i];
    }
    
    int cnt = l;
    int st = 0;
    int ed = l-1;
    
    int etSum = 0;
    int ebSum = 0;
    
    while (ed < n) {
        while (cnt > u || (cnt > l && v[st] < 1.0*tSum/bSum)) {
            tSum -= t[st];
            bSum -= b[st];
            etSum -= t[st];
            ebSum -= b[st];
            cnt -= 1;
            st += 1;
        }
        
        if (cnt > l && 1.0*etSum/ebSum < v[ed-l+1]) {
            tSum -= etSum;
            bSum -= ebSum;
            etSum = 0;
            ebSum = 0;
            cnt = l;
            st = ed-l+1;
        }
        
        
        ans = max(ans, 1.0*tSum/bSum);
        
        if (ed != n-1) {
            tSum += t[ed+1];
            bSum += b[ed+1];
            etSum += t[ed+1-l];
            ebSum += b[ed+1-l];
        }
        ed += 1;
        cnt += 1;
    }

    fout << fixed << setprecision(2) << ans;
    
    return 0;
}