Pagini recente » Cod sursa (job #2751088) | Cod sursa (job #2678791) | Cod sursa (job #1499393) | Cod sursa (job #1500391) | Cod sursa (job #648381)
Cod sursa(job #648381)
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int dq[500001] , v[50001] , s[50001] , bk , fr , N , K;
int pos1 , pos2 , dim , smax;
int main()
{
fin>>N>>K;
for(int i = 1;i<=N;++i)
fin>>v[i] , s[i]+=s[i-1] + v[i];
dq[++bk] = 1; fr = 1;
smax = s[K] , pos1 = 1, pos2 = K;
for(int i = 1;i<=N;++i)
{
if(s[i+K-1] - s[dq[fr]] > smax)
smax = s[i+K-1] - s[dq[fr]] , pos1 = dq[fr] + 1 , pos2 = i + K-1;
while(fr<=bk && s[i]<=s[dq[bk]]) bk--;
dq[++bk] = i;
}
fout<<pos1<<" "<<pos2<<" "<<smax;
return 0;
}