Pagini recente » Cod sursa (job #1685315) | Cod sursa (job #2887798) | Cod sursa (job #2197238) | Cod sursa (job #2403480) | Cod sursa (job #1770045)
#include <iostream>
#include <fstream>
using namespace std;
int sum[50001];
int main()
{
ifstream in("secv2.in");
ofstream out("secv2.out");
int n,k,smax,sc,pc,umax,pmax,i,a[50001];
in>>n>>k;
for(i=1; i<=n; i++)
{
in>>a[i];
sum[i] = sum[i-1] + a[i];
}
sc = smax = sum[k];
pc = pmax = 1;
umax = k;
for(i=1+k; i<=n; i++)
{
in>>a[i];
sum[i] = sum[i-1] + a[i];
if (sum[i] - sum[i-k] > sc + a[i])
{
sc = sum[i] - sum[i-k];
pc = i - k + 1;
}
else
sc += a[i];
if (sc > smax)
{
smax = sc;
pmax = pc;
umax = i;
}
}
out<<pmax<<" "<<umax<< " "<<smax;
}
/*
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"
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]
*/