Cod sursa(job #2472259)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 12 octombrie 2019 10:41:43
Problema Secventa 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <limits.h>

using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

const int MAXN = 5 * 1e5;
int arr[MAXN], sum[MAXN], n, k;

void read() {
    fin >> n >> k;
    for (int i = 1; i <= n; ++i)
        fin >> arr[i];
}

void preprocess() {
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + arr[i];
}

void solve() {
    int min = INT_MAX, indMin = 0, max = sum[k], ind1 = 1, ind2 = k;
    for (int i = k + 1; i <= n; ++i) {
        if (min > sum[i - k])
            min = sum[i - k], indMin = i - k + 1;
        if (max < sum[i])
            max = sum[i], ind1 = 1, ind2 = i;
        if (max < sum[i] - min)
            max = sum[i] - min, ind1 = indMin, ind2 = i;
    }
    cout << ind1 << ' ' << ind2 << ' ' << max << '\n';
}

int main() {
    read();
    preprocess();
    solve();
    return 0;
}