Pagini recente » Cod sursa (job #1760447) | Cod sursa (job #223509) | Cod sursa (job #90868) | Cod sursa (job #1200575) | Cod sursa (job #943843)
Cod sursa(job #943843)
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
int nums[50005], dpl[50005], dpr[50005], ml[50005], mr[50005];
int main(){
ifstream in("secv2.in");
ofstream out("secv2.out");
int n, k;
in >> n >> k;
for(int i = 1; i <= n; ++i){
in >> nums[i];
dpl[i] = dpr[i] = nums[i];
if(dpl[i - 1] > 0){
ml[i] = ml[i - 1] + 1;
dpl[i] += dpl[i - 1];
}
else
ml[i] = 1;
}
for(int i = n; i > 0; --i)
if(dpr[i + 1] > 0){
mr[i] = mr[i + 1] + 1;
dpr[i] += dpr[i + 1];
}
else
mr[i] = 1;
for(int i = 1; i <= n; ++i)
nums[i] = nums[i] + nums[i - 1];
int ans = -2e9, x, y;
for(int i = k; i <= n; ++i){
int lf = i - k + 1, rt = i, pans = nums[i] - nums[lf - 1];
if(dpl[lf - 1] > 0){
pans += dpl[lf - 1];
lf -= ml[lf - 1];
}
if(dpr[i + 1] > 0){
rt += mr[i + 1];
pans += dpr[i + 1];
}
if(pans > ans){
ans = pans;
x = lf;
y = rt;
}
}
out << x << " " << y << " " << ans;
return 0;
}