Cod sursa(job #2005631)

Utilizator richieYRichie Yeung richieY Data 27 iulie 2017 17:51:16
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <deque>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");
int main() {
    int l, u, n;
    fin >> n >> l >> u;
    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;
    int lTSum = 0;
    int lBSum = 0;
    double ans = 0;
    for (int i = 0; i < l; i++) {
        tSum += t[i];
        bSum += b[i];
    }
    deque<int> cand;
    for (int i = 0; i < n-l; i += 1) {
        cerr << i << '\n';
        tSum += t[i+l];
        bSum += b[i+l];
        tSum -= t[i];
        bSum -= b[i];
        
        if (!cand.empty()) {
            int fr = cand.front();
            if ((i+l-1) - fr + 1 > u) {
                cand.pop_front();
                if (!cand.empty()) {
                    int nfr = cand.front();
                    // update to next candidate
                    while (fr <= nfr) {
                        lTSum -= t[fr];
                        lBSum -= b[fr]; 
                        fr += 1;
                    }
                    // TODO need to swap this so that pop first then insert.
                } else {
                    lTSum = 0;
                    lBSum = 0;
                }
            }
        }
        cerr << "size before "<< cand.size() << '\n';
        int currTSum = t[i];
        int currBSum = b[i];
        int p = i;
        while (!cand.empty()) {
            int bk = cand.back();
            while (bk != p) {
                cerr << "p: " << p << '\n';
                currTSum += t[p-1];
                currBSum += b[p-1];
                p -= 1;
            }
            if (1.0 * currTSum / currBSum < 1.0 * tSum / bSum) {
                cand.pop_back();
            } else {
                break;
            }
        }
        
        cand.push_back(i);
        lTSum += t[i];
        lBSum += b[i];
        
        ans = max(ans, max(1.0*(tSum+lTSum)/(bSum+lBSum), 1.0*tSum/bSum));
    }
    
    fout << fixed << setprecision(2) << ans;
    
    return 0;
}