Cod sursa(job #2657662)

Utilizator el3vat1onAdrian Pop el3vat1on Data 11 octombrie 2020 14:07:15
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;

int main(int argc, char *argv[]) {
    ifstream in("secv2.in");
    int n, k, a[50000];
    in >> n >> k;
    for (int i = 0; i < n; i++) in >> a[i];
    in.close();

    int dp[50000];
    int seq[50000];
    int start = 0;
    for (int i = 0; i < k; i++)  {
        start += a[i];
        seq[i] = 0;
    }
    dp[k - 1] = start;
    seq[k - 1] = k - 1;
    for (int i = k; i < n; i++) {
        dp[i] = dp[i - 1] - a[i - k] + a[i];
        seq[i] = k - 1;
    }

    for (int i = k; i < n; i++) {
        if (dp[i - 1] > dp[i] || dp[i - 1] + a[i] > dp[i]) {
                dp[i] = dp[i - 1] + a[i];
                seq[i] = seq[i - 1] + 1;
        }
    }

    int max = dp[k - 1];
    int pos = k - 1;
    for (int i = k; i < n; i++) {
        if (max <= dp[i]) {
            max = dp[i];
            pos = i;
        }
    }

    ofstream out("secv2.out");
    out << pos + 1 - seq[pos] << " " << pos + 1 << " " << max;
    out.close();

    return 0;
}