Cod sursa(job #2629376)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 20 iunie 2020 13:11:56
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"


/// {1, 2}, {1, 3} cele mai mici sume -> cautam care este suma {2, 3} -> aflam cel mai mic numar
/// {2, 3} este in primele n sume

const int N = 5e4;
int sum[1 + N];

int main () {
    freopen ("secv2.in", "r", stdin);
    freopen ("secv2.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, k;
    cin >> n >> k;
    int bestIndex = 0;
    int ans = - (1 << 30), ansL = 0, ansR = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
        if (i > k && sum[bestIndex] > sum[i - k])
            bestIndex  = i - k;
        if (sum[i] - sum[bestIndex] > ans) {
            ans = sum[i] - sum[bestIndex];
            ansL = bestIndex + 1;
            ansR = i;
        }
    }
    cout << ansL << " " << ansR << " " << ans << "\n";
    return 0;
}