Pagini recente » Cod sursa (job #3177580) | Cod sursa (job #2174) | Monitorul de evaluare | Cod sursa (job #3282272) | Cod sursa (job #3163886)
#include <fstream>
#include <deque>
using namespace std;
ifstream cin ("secv3.in");
ofstream cout ("secv3.out");
int main ()
{
int lungime_totala , lungime_minima , lungime_maxima;
cin >> lungime_totala >> lungime_minima >> lungime_maxima;
int factor[2][30001];
for (int indice_1 = 0 ; indice_1 < 2 ; indice_1++) {
factor[indice_1][0] = 0;
for (int indice_2 = 1 ; indice_2 <= lungime_totala ; indice_2++) {
cin >> factor[indice_1][indice_2]; factor[indice_1][indice_2] += factor[indice_1][indice_2 - 1];
}
}
deque <int> optiuni;
optiuni.push_back(0);
pair <int , int> maxim = make_pair(factor[0][lungime_minima] , factor[1][lungime_minima]);
for (int indice = lungime_minima + 1 ; indice <= lungime_totala ; indice++)
{
optiuni.push_back(indice - lungime_minima);
if (optiuni.front() == indice - lungime_maxima - 1)
{ optiuni.pop_front(); }
while (optiuni.size() > 1) {
const int initial = optiuni.back(); optiuni.pop_back();
pair <int , int> optiune_1 = make_pair(factor[0][indice] - factor[0][initial] , factor[1][indice] - factor[1][initial]);
pair <int , int> optiune_2 = make_pair(factor[0][indice] - factor[0][optiuni.back()] , factor[1][indice] - factor[1][optiuni.back()]);
if (1LL * optiune_1.first * optiune_2.second <= 1LL * optiune_2.first * optiune_1.second) { optiuni.push_back(initial); break; }
}
pair <int , int> actual = make_pair(factor[0][indice] - factor[0][optiuni.back()] , factor[1][indice] - factor[1][optiuni.back()]);
if (1LL * maxim.first * actual.second < 1LL * actual.first * maxim.second) { maxim = actual; }
}
cout << maxim.first / maxim.second << '.' << 100 * maxim.first / maxim.second % 100;
cout.close(); cin.close();
return 0;
}