Cod sursa(job #3286460)

Utilizator blidar_lucian1Adrian Popescu blidar_lucian1 Data 14 martie 2025 11:13:29
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int n, k;
long long a[50001];

int main() {
    f >> n >> k;
    for (int i = 1; i <= n; ++i) {
        f >> a[i];
    }

    long long sum = 0, maxSum = LLONG_MIN;
    int start = 1, end = k, bestStart = 1, bestEnd = k;

    // Suma inițială pentru primele K elemente
    for (int i = 1; i <= k; ++i) {
        sum += a[i];
    }
    maxSum = sum;

    // Fereastră glisantă pentru restul elementelor
    for (int i = k + 1; i <= n; ++i) {
        sum += a[i];
        if (sum > maxSum) {
            maxSum = sum;
            bestStart = start;
            bestEnd = i;
        }

        // Scădem elementul de la începutul ferestrei
        sum -= a[start];
        start++;

        // Extindem secvența curentă
        long long extSum = sum;
        int extEnd = i;
        for (int j = i + 1; j <= n; ++j) {
            extSum += a[j];
            if (extSum > maxSum) {
                maxSum = extSum;
                bestStart = start;
                bestEnd = j;
            }
        }
    }

    g << bestStart << " " << bestEnd << " " << maxSum << "\n";
    return 0;
}