Pagini recente » Cod sursa (job #2875474) | Cod sursa (job #2554092) | Cod sursa (job #1274520) | Cod sursa (job #1542519) | Cod sursa (job #1248702)
#include <fstream>
#define DIM 100005
#define x first
#define y second
#define infile "secv2.in"
#define outfile "secv2.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int V[DIM], D[DIM], Partial_Sum_k[DIM];
int n, k;
pair<int, int> Pos[DIM];
int main() {
f >> n >> k;
for (int i = 1; i <= n; ++i)
f >> V[i];
for (int i = 1; i <= k; ++i)
Partial_Sum_k[k] += V[i];
for (int i = k + 1; i <= n; ++i)
Partial_Sum_k[i] = Partial_Sum_k[i - 1] - V[i - k] + V[i];
Pos[k].x = 1;
Pos[k].y = k;
D[k] = Partial_Sum_k[k];
int SOL = D[k], sol_pos_start = 1, sol_pos_end = k;
for (int i = k + 1; i <= n; ++i) {
if (Partial_Sum_k[i] > D[i - 1] + V[i]) {
D[i] = Partial_Sum_k[i];
Pos[i].x = i - k + 1;
Pos[i].y = i;
}
else {
D[i] = D[i - 1] + V[i];
Pos[i].x = Pos[i - 1].x;
Pos[i].y = i;
}
if (SOL < D[i]) {
SOL = D[i];
sol_pos_start = Pos[i].x;
sol_pos_end = Pos[i].y;
}
}
g << sol_pos_start << " " << sol_pos_end << " " << SOL;
return 0;
}
//Trust me, I'm the Doctor!