Cod sursa(job #2726032)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 20 martie 2021 09:02:34
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;

int n, k, dp[50100], a[50100], pozitie_maxim, maxim = INT_MIN, pozitie_minim, minim = INT_MAX;

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

int main() {
    fin.tie(0);
    ios::sync_with_stdio(0);
    fin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    dp[0] = 0;
    for (int j = 1; j <= n; ++j) {
        dp[j] = a[j] + dp[j - 1];
        if (dp[j] > maxim) {
            maxim = dp[j];
            pozitie_maxim = j;
        }
    }
    if (maxim > 0) {
        int Beg, End, best_sum = INT_MIN;
        for (int j = pozitie_maxim - 1; j >= 1; --j) {
            if (pozitie_maxim - j >= k && dp[pozitie_maxim] - dp[j] + a[j] > best_sum) {
                best_sum = dp[pozitie_maxim] - dp[j] + a[j];
                Beg = j;
                End = pozitie_maxim;
            }
        }
        for (int j = pozitie_maxim + 1; j <= n; ++j) {
            if (j - pozitie_maxim >= k && dp[j] - dp[pozitie_maxim] + a[pozitie_maxim] > best_sum) {
                best_sum = dp[j] - dp[pozitie_maxim] + a[pozitie_maxim];
                Beg = pozitie_maxim;
                End = j;
            }
        }
        fout << Beg << " " << End << " " << best_sum;
    }
    else {
        int Beg = 0, End = 0, best_sum = INT_MIN;
        pozitie_minim = n;
        for (int j = pozitie_minim - 1; j >= 1; --j) {
            if (pozitie_minim - j + 1 >= k && dp[pozitie_minim] - dp[j] + a[j] > best_sum) {
                best_sum = dp[pozitie_minim] - dp[j] + a[j];
                Beg = j;
                End = pozitie_minim;
            }
        }
        for (int j = pozitie_minim + 1; j <= n; ++j) {
            if (j - pozitie_minim >= k && dp[j] - dp[pozitie_minim] + a[pozitie_minim] > best_sum) {
                best_sum = dp[j] - dp[pozitie_minim] + a[pozitie_minim];
                Beg = pozitie_minim;
                End = j;
            }
        }
        fout << Beg << " " << End << " " << best_sum;
    }
    return 0;
}