Pagini recente » Cod sursa (job #2541383) | Cod sursa (job #519318) | Cod sursa (job #445655) | Cod sursa (job #828600) | Cod sursa (job #2726032)
#include <bits/stdc++.h>
using namespace std;
int n, k, dp[50100], a[50100], pozitie_maxim, maxim = INT_MIN, pozitie_minim, minim = INT_MAX;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int main() {
fin.tie(0);
ios::sync_with_stdio(0);
fin >> n >> k;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
}
dp[0] = 0;
for (int j = 1; j <= n; ++j) {
dp[j] = a[j] + dp[j - 1];
if (dp[j] > maxim) {
maxim = dp[j];
pozitie_maxim = j;
}
}
if (maxim > 0) {
int Beg, End, best_sum = INT_MIN;
for (int j = pozitie_maxim - 1; j >= 1; --j) {
if (pozitie_maxim - j >= k && dp[pozitie_maxim] - dp[j] + a[j] > best_sum) {
best_sum = dp[pozitie_maxim] - dp[j] + a[j];
Beg = j;
End = pozitie_maxim;
}
}
for (int j = pozitie_maxim + 1; j <= n; ++j) {
if (j - pozitie_maxim >= k && dp[j] - dp[pozitie_maxim] + a[pozitie_maxim] > best_sum) {
best_sum = dp[j] - dp[pozitie_maxim] + a[pozitie_maxim];
Beg = pozitie_maxim;
End = j;
}
}
fout << Beg << " " << End << " " << best_sum;
}
else {
int Beg = 0, End = 0, best_sum = INT_MIN;
pozitie_minim = n;
for (int j = pozitie_minim - 1; j >= 1; --j) {
if (pozitie_minim - j + 1 >= k && dp[pozitie_minim] - dp[j] + a[j] > best_sum) {
best_sum = dp[pozitie_minim] - dp[j] + a[j];
Beg = j;
End = pozitie_minim;
}
}
for (int j = pozitie_minim + 1; j <= n; ++j) {
if (j - pozitie_minim >= k && dp[j] - dp[pozitie_minim] + a[pozitie_minim] > best_sum) {
best_sum = dp[j] - dp[pozitie_minim] + a[pozitie_minim];
Beg = pozitie_minim;
End = j;
}
}
fout << Beg << " " << End << " " << best_sum;
}
return 0;
}