Cod sursa(job #2005662)

Utilizator richieYRichie Yeung richieY Data 27 iulie 2017 18:44:53
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 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<bool> cand(n, false);
    for (int i = 0; i < n; i += 1) {
        fin >> t[i];
    }
    
    for (int i = 0; i < n; i += 1) {
        fin >> b[i];
    }
    
    
    int tSum = 0;
    int bSum = 0;
    for (int i = 0; i < l; i++) {
        tSum += t[i];
        bSum += b[i];
    }
    double ans = 1.0 * tSum / bSum;
    
    cand[0] = true;
    int currCand = 0;
    int lTSum = 0;
    int lBSum = 0;
    for (int i = 1; i <= n-l; i += 1) {
        // starts at i, ends at i+l-1
        tSum += t[i+l-1];
        bSum += b[i+l-1];
        tSum -= t[i-1];
        bSum -= b[i-1];
        lTSum += t[i-1];
        lBSum += b[i-1];
        cand[i-1] = true;
        if ((i+l-1) - currCand + 1 > u) {
            cand[currCand] = false;
            while (!cand[currCand] && lTSum > 0) {
                lTSum -= t[currCand];
                lBSum -= b[currCand];
                currCand += 1;
            }
        }
        int p = i-1;
        int pTSum = 0;
        int pBSum = 0;
        while (p > currCand) {
            pTSum += t[p];
            pBSum += b[p];
            if (cand[p]) {
                if (1.0 * pTSum / pBSum > 1.0 * tSum / bSum) {
                    break;
                } else {
                    if (pTSum % tSum == 0 && pBSum % bSum == 0) {
                        if (pTSum / tSum == pBSum / bSum) {
                            // if gives the same fraction, prefer one with larger weighting
                            break;
                        }
                    }
                    // otherwise
                    cand[p] = false;
                }
            }
            p -= 1;
        }
        
        ans = max(ans, max(1.0*(tSum+lTSum)/(bSum+lBSum), 1.0*tSum/bSum));
    }
    
    fout << fixed << setprecision(2) << ans;
    
    return 0;
}