Pagini recente » Cod sursa (job #2407266) | Cod sursa (job #2814165) | Cod sursa (job #68493) | Cod sursa (job #2591455) | Cod sursa (job #2891001)
#include<bits/stdc++.h>
using namespace std;
int n,sol = INT_MIN,k,indexDreapta,indexStanga,indexFinalStanga;
int sp[6000005],mp[6000005];
int main()
{
ifstream fin("secv2.in");
ofstream fout("secv2.out");
fin>>n>>k;
sp[0]=0;
mp[0] = 0;
for(int i=1;i<=n;i++)
{
int x;
fin>>x;
sp[i] = sp[i-1] + x;
if(i >= k){
int val = sp[i] - mp[i-k];
if(val > sol){
sol = val;
indexDreapta = i;
indexFinalStanga = indexStanga;
}
}
/**
Ce se schimba de la i la i+1
Pentru i, ne intereseaza ca lungimea sa fie >=k, deci ne intereseaza sumele partiale de la sp[0] pana la sp[i-k]
Pentru i+1, ne intereseaza ca lungimea sa fie >=k, deci ne intereseaza sumele partiale de la sp[0] pana la sp[i-k+1]
Va trebui sa adaugama sp[i-k+1]
**/
if(i>=k && sp[i-k+1] < mp[i-k] ){
indexStanga = i-k+2;
}
mp[i] = min(mp[i-1],sp[i]);
}
fout<<indexFinalStanga<<" "<<indexDreapta<<" "<<sol<<'\n';
return 0;
}