Ideone.com

fork download

copy

#include<iostream>
#include<vector>
using namespace std;
const int MAX_N = 100'000;
int a_sum[MAX_N + 1];
int n, d;
int l, r;
bool good(double mid) {
    double mi = 1e18;
    double mi_pos = -1;
    for(int i = d; i <= n; i++) {
        int j = i - d;
        cout << j * mid << endl; 
        if(mi > a_sum[j] - j * mid) {
            mi = a_sum[j] - j * mid;
            mi_pos = j + 1;
        }
        if(a_sum[i] - i * mid >= mi) {
            l = mi_pos;
            r = i;
            return 1;
        }
    }
    return 0;
}
int main() {
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a_sum[i] = x + a_sum[i - 1];
    }
    double low = -1, hi = 100;
    for(int i = 0; i < 60; i++) {
        double mid = (low + hi) / 2;
        if(good(mid)) {
            low = mid;
        } else {
            hi = mid;
        }
    }
    cout << l << ' ' << r << '\n';
}

Success #stdin #stdout 0.01s 5284KB

stdin

copy

6 2
3 1 8 5 7 2

stdout

copy

https://ideone.com/JlNCkp

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language