Cod sursa(job #2835329)

Utilizator CiuiGinjoveanu Dragos Ciui Data 18 ianuarie 2022 15:27:46
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

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

const int MAX_SIZE = 50001;
int sp[MAX_SIZE];

int main() {
    int n, v[MAX_SIZE], k;
    fin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        sp[i] = sp[i - 1] + v[i];
    }
    int min = 0, maxSum = -1250000000, minIndex = 0, startIndex = 0, stopIndex = 0;
    for (int i = 1; i <= n; ++i) {
        if (sp[i] - min > maxSum && i - minIndex >= k) {
            maxSum = sp[i] - min;
            startIndex = minIndex + 1;
            stopIndex = i;
        }
        if (min > sp[i]) {
            min = sp[i];
            minIndex = i;
        }
    }
    fout << startIndex << " " << stopIndex << " " << maxSum;
}
/*
// test 12
am facut urmatoarea observatie:

1 1 -> 0
2 2 -> 2
3 3 -> 4
4 4 -> 6
...
10 10 -> 18

20000 2
-> 3
 
2 20000
-> 2

1 1000
-> 0

1000 1
-> 1
 
9 6
 -> 11
 
6 9
 -> 10



*/