Cod sursa(job #1561705)

Utilizator rexlcdTenea Mihai rexlcd Data 4 ianuarie 2016 14:13:53
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

int n,k;
int dp[50002],vmin[50002];

int main()
{
    ifstream f("secv2.in");
    ofstream g("secv2.out");
    f>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        dp[i]=dp[i-1]+x;
        if(dp[i]<dp[vmin[i-1]])
            vmin[i]=i;
        else
            vmin[i]=vmin[i-1];
    }
    int best=dp[k],st=1,dr=k;
    for(int i=k+1;i<=n;i++)
    {
        if(dp[i]-dp[vmin[i-k]]>best)
        {
            best=dp[i]-dp[vmin[i-k]];
            dr=i;
            st=vmin[i-k]+1;
        }
    }
    g<<st<<" "<<dr<<" "<<best<<'\n';
    f.close();
    g.close();
    return 0;
}