Pagini recente » Cod sursa (job #2027313) | Cod sursa (job #2884139) | Cod sursa (job #85709) | Cod sursa (job #2156063) | Cod sursa (job #2714884)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
int sumpart[50005],a[50005],smax,s,i,slast,stot,n,k,xc = 1,x = 1,y;
int main()
{
in >> n >> k;
y = k;
for (i = 1; i <= n; i++)
{
in >> a[i];
s += a[i];
sumpart[i] = s;
}
smax = s = sumpart[k];
for (i = k + 1; i <= n; i++)
{
stot = s + a[i];
slast = sumpart[i] - sumpart[i - k];
s = max(stot,slast);
if (s == slast)
xc = i - k + 1;
if (s > smax)
{
smax = s;
x = xc;
y = i;
}
}
out << x << " " << y << " " << smax;
return 0;
}
/*
la pasul i>k:
la inceput sc este cea mai mare suma care se poate forma cu cel putin k termeni si se termina pe pozitia i-1
vrei sa obtii cea mai mare suma care se poate forma cu cel putin k termeni si se termina pe pozitia i
adunand v[i] la sc obtii cea mai mare suma care se poate forma cu cel puin k+1 termeni si se termina pe pozitia i
pemtru a trece de la "cel putin k+1" la "cel putin k" trebuie luat in considerare "exact k"
{1}
adica sc devine max(sc+v[i], suma ultimilor exact k)
suma ultimilor exact k este sum[i] - sum[i-k]
unde sum[i] = v[1] + v[2] + ... + v[i]
*/