Pagini recente » Cod sursa (job #1605362) | Borderou de evaluare (job #1567345) | Cod sursa (job #306611) | Cod sursa (job #2624221) | Cod sursa (job #2765027)
#include <iostream>
#include <fstream>
#include <string.h>
#include <climits>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
int v[50001];
struct structura {
long long val; // suma maxima a subsecv care se termina in i
int lung_cur; // lungimea subsecv respective
};
structura v_final[50001];
void afisare(int n) {
for (int i = 1; i <= n; i++)
cout << v_final[i].val << " ";
cout << endl;
}
int main() {
int n, k, i;
in >> n >> k;
for (i = 1; i <= n; i++) {
in >> v[i];
}
for (int i = 1; i <= k; i++) {
v_final[k].val += v[i];
}
v_final[k].lung_cur = k;
long long s_max = v_final[k].val, poz_max = k;
for (i = k + 1; i <= n; i++) {
if (v_final[i - 1].val < 0 && v_final[i - 1].lung_cur == k) {
v_final[i].val = v_final[i - 1].val + v[i] - v[i - k];
v_final[i].lung_cur = k;
}
/* if (v_final[i - 1].val < 0 && v_final[i - 1].lung_cur > k) {
while (true)
cout << 'z';
}*/
if (v_final[i - 1].val >= 0) {
v_final[i].val = v_final[i - 1].val + v[i];
v_final[i].lung_cur = v_final[i - 1].lung_cur + 1;
}
if (v_final[i].val > s_max) {
s_max = v_final[i].val;
poz_max = i;
}
}
out << poz_max - v_final[poz_max].lung_cur + 1 << " " << poz_max << " " << s_max;
} // vad daca-s mai multe