Pagini recente » Cod sursa (job #1748628) | Cod sursa (job #1127628) | Cod sursa (job #1500525) | Cod sursa (job #2124769) | Cod sursa (job #2457598)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
typedef long long ll;
int x[50001],n,k;
struct sol
{
int st;
ll sum;
};
sol make(int st,ll sum)
{
sol rez;
rez.st=st;
rez.sum=sum;
return rez;
}
sol kalvin[50001];
void solve()
{
kalvin[1]=make(1,x[1]);
for(int i=2;i<=n;i++)
{
if(kalvin[i-1].sum>=0)
kalvin[i]=make(kalvin[i-1].st,kalvin[i-1].sum+x[i]);
else
kalvin[i]=make(i,x[i]);
}
ll curentsum=0;
ll bestsum=0;
int st,bst,bdr;
st=bst=1;
bdr=k;
for(int i=1;i<=k;i++)
bestsum=curentsum=curentsum+x[i];
for(int i=k+1;i<=n;i++)
{
curentsum=curentsum+x[i]-x[i-k];
st=i-k+1;
int compara=curentsum;
if(kalvin[i-k].sum>0)
{
st=kalvin[i-k].st;
compara+=kalvin[i-k].sum;
}
if(compara>bestsum)
{
bestsum=compara;
bst=st;
bdr=i;
}
}
g<<bst<<' '<<bdr<<' '<<bestsum;
}
int main()
{
f>>n>>k;
for(int i=1;i<=n;i++)
f>>x[i];
solve();
f.close();
g.close();
return 0;
}