Cod sursa(job #3218000)

Utilizator BoggiGurau Bogdan Boggi Data 25 martie 2024 17:37:14
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <vector>
using namespace std;

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

struct secv {
    int st, fn, sum;
} maxim, curent;

int main() {
    int N, K;
    fin >> N >> K;
    vector<int> sir, sp;
    sir = sp = vector<int>(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        fin >> sir[i];
        sp[i] = sp[i - 1] + sir[i];
    }
    maxim.sum = sp[K];
    maxim.st = 1, maxim.fn = K;
    curent.sum = sp[K];
    curent.st = 1, curent.fn = K;
    for (int i = K + 1; i <= N; ++i) {
        if (maxim.sum < curent.sum) {
            maxim = curent;
        }
        if (curent.sum + sir[i] < sp[i] - sp[i - K]) {
            curent.sum = sp[i] - sp[i - K];
            curent.st = i - K + 1;
            curent.fn = i;
        } else {
            curent.sum += sir[i];
            ++curent.fn;
        }
    }

    fout << maxim.st << ' ' << maxim.fn << ' ' << maxim.sum;
}