Pagini recente » Cod sursa (job #1037068) | Cod sursa (job #1475931) | Cod sursa (job #1381079) | Cod sursa (job #2673863) | Cod sursa (job #369532)
Cod sursa(job #369532)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
int main() {
fstream f1, f2;
deque<pair<long long, long long> > deq;
long long n, k, elem[50001], sum[50001], i, j, max=-1250075002, start, end;
f1.open("secv2.in", ios::in);
f1>>n>>k; sum[0]=0;
f1>>elem[1]; sum[1]=elem[1];
for(i=2; i<=n; i++) {
f1>>elem[i];
sum[i]=sum[i-1]+elem[i];
}
f1.close();
for(i=k; i<=n; i++) {
//calculez sum[i]-min(sum[j])
//adaug i-k
while(!deq.empty() && deq.back().first>sum[i-k]) {
deq.pop_back();
}
deq.push_back(make_pair(sum[i-k], i-k));
if(sum[i]-deq.front().first>max) {
max=sum[i]-deq.front().first;
start=deq.front().second+1;
end=i;
}
}
f2.open("secv2.out", ios::out);
if(n==k) { f2<<1<<" "<<n<<" "<<sum[n]<<endl; }
else { f2<<start<<" "<<end<<" "<<max<<endl; }
f2.close();
return 0;
}