Pagini recente » Diferente pentru problema/interclas intre reviziile 11 si 10 | Diferente pentru problema/interclas intre reviziile 12 si 11 | Diferente pentru problema/interclas intre reviziile 13 si 12 | Cod sursa (job #3360593) | Cod sursa (job #3361002)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
long long n, k, v[200005], sp[200005], suma, maxim = -1000000000000000000LL, sumaUltimelorKminus1, sfarsit, inceput, inceputCurent;
int main() {
fin >> n >> k;
for (int i = 1; i <= n; i ++) {
fin >> v[i];
}
/// sp[i] - sp[x] sa fie maxim => sp[x] sa fie minim
/// i - x >= k <=> x <= i - k
long long sumaMinima = 0;
inceputCurent = 0;
for(int i = 1; i <= n; i ++) {
sp[i] = sp[i-1] + v[i];
if (i >= k) {
if(sp[i] - sumaMinima > maxim) {
maxim = sp[i] - sumaMinima;
sfarsit = i;
inceput = inceputCurent;
}
if(sp[i-k] < sumaMinima) {
sumaMinima = sp[i-k];
inceputCurent = i-k+1;
}
}
}
fout << inceput << ' ' << sfarsit << ' ' << maxim;
}
/*
k=3
0 1 2 3 -7 8 2
0 1 -2 3 7 8 2
*/