Pagini recente » Cod sursa (job #172137) | Cod sursa (job #3310400) | Cod sursa (job #1551316) | Cod sursa (job #3312406) | Cod sursa (job #3322391)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n, k;
fin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) fin >> a[i];
// prefix sums of size n+1
// pref[i] = sum of a[0..i-1]
vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; i++)
pref[i] = pref[i - 1] + a[i - 1];
// we want: max(pref[dr] - pref[st]) with dr - st >= k
int bestSum = -1e9, bestL = 1, bestR = k;
// keep track of the minimum prefix sum available for the st candidate
int minPref = 0; // pref[0]
int minPrefPos = 0;
for (int dr = k; dr <= n; dr++) {
// the candidate st can go from 0..dr-k
int stLimit = dr - k;
// update minimum prefix sum up to stLimit
if (pref[stLimit] < minPref) {
minPref = pref[stLimit];
minPrefPos = stLimit;
}
int sum = pref[dr] - minPref;
if (sum > bestSum) {
bestSum = sum;
bestL = minPrefPos + 1;
bestR = dr;
}
}
fout << bestL << " " << bestR << " " << bestSum;
}