Cod sursa(job #2513152)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 22 decembrie 2019 14:29:52
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, k, sum[50005], ans= -100000, l, r;
pair <int, int> dp[50005];
int main()
{
    fin >> n >> k;

    for(int i = 1; i <= n; i++)
    {

        int x;
        fin >> x;
        sum[i] = x+sum[i-1];
        if(dp[i-1].first <= 0)
        {
            dp[i].first = x;
            dp[i].second = i;
        }
        else
        {
            dp[i].first = dp[i-1].first + x;
            dp[i].second = dp[i-1].second;
        }

        if(k > i) continue;
        if(dp[i-k].first > 0)
        {
            if(dp[i-k].first+sum[i]-sum[i-k] > ans)
            {
                ans = dp[i-k].first+sum[i]-sum[i-k];
                l = dp[i-k].second;
                r = i;
            }
        }
        else
        {
            if(sum[i]-sum[i-k] > ans)
            {
                ans = sum[i]-sum[i-k];
                l = i-k+1;
                r = i;
            }
        }
    }

    fout << l << " " << r << " "<<ans;

    return 0;
}