Pagini recente » Cod sursa (job #550592) | Cod sursa (job #920383) | Cod sursa (job #2559273) | Cod sursa (job #3201194) | Cod sursa (job #307706)
Cod sursa(job #307706)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int main()
{
int n,k,min,max,lung,nr,ult,i;
f>>n>>k;
vector<int> s(n+1,0);
for (i=1;i<=n;i++)
{
f>>s[i];
s[i]=s[i]+s[i-1];
}
min=0; nr=0;
max=s[k]; lung=k; ult=k;
for (i=k+1;i<=n;i++)
// suma subsirului cu k elemente ce se termina cu a[i] este s[i]-s[i-k]
// deci pentru a gasi suma maxima cu cel putin k elemente ce se termina cu elementul i
// trebuie sa gasim
// max{s[i]-s[i-k], s[i]-s[i-k-1],..., s[i]-s[1], s[i]} =
// = s[i]-min{s[i-k],s[i-k-1],...,s[1],0}
{
if (s[i-k]<min)
{
min=s[i-k]; nr=i-k;
}
if (s[i]-min>max)
{
max=s[i]-min;
ult=i; lung=i-nr;
}
}
g<<ult-lung+1<<" "<<ult<<" "<<max;
g.close();
return 0;
}