Cod sursa(job #1727965)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 11 iulie 2016 23:12:31
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
const int maxn = 50005;
int d[maxn];
int p[maxn];
int v[maxn];
int main()
{
    int n, k;
    in >> n >> k;
    bool ok = 0;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i];
        if(v[i] >= 0)
            ok = 1;
    }
    if(!ok)
    {
        int s = 0;
        int st = 1;
        int dr = k;
        for(int i = 1; i <= k; i++)
            s += v[i];
        int smax = s;
        for(int i = k + 1; i <= n; i++)
        {
            s += v[i];
            if(smax < s)
            {
                smax = s;
                st = i - k + 1;
                dr = i;
            }
        }
        out << st << " " << dr << " " << smax << "\n";
        return 0;
    }
    for(int i = 1; i <= n; i++)
        p[i] = p[i-1] + v[i];
    int mn = (1 << 30);
    for(int i = k; i <= n; i++)
    {
        mn = min(mn, p[i-k]);
        d[i] = max(d[i-1], p[i] - mn);
    }
    int mx = -1000000;
    for(int i = 1; i <= n; i++)
        mx = max(mx, d[i]);
    int dr = 0;
    for(int i = 1; i <= n; i++)
    {
        if(d[i] == mx)
        {
            dr = i;
            break;
        }
    }
    int sum = 0;
    int st = dr;
    while(sum != mx || dr - st + 1 < k)
    {
        sum += v[st];
        st--;
    }
    out << st + 1 << " " << dr << " " << mx << "\n";
    return 0;
}