Pagini recente » Cod sursa (job #2619571) | Cod sursa (job #2717779) | Cod sursa (job #1586000)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
const int dmax = 50000;
int a[dmax + 1];
int best[dmax + 1]; //best[i] == SUMA MAXIMA A UNEI SUBSECVENTE CE SE TERMINA PE POZITIA i
int NR[dmax + 1]; //NR[i] == LUNGIMEA UNEI SSM CE SE TERMINA PE POZITIA i
int N, K;
int main()
{
int i, best_Sum = 0, p, u;
bool GASIT = false;
in >> N >> K;
for(i = 1; i <= N; i++) in >> a[i];
for(i = 1; i <= N; i++)
{
best[i] = a[i];
NR[i] = 1;
if(best[i] < best[i - 1] + a[i])
{
best[i] = best[i - 1] + a[i];
NR[i] = NR[i - 1] + 1;
}
}
for(i = 1; i <= K; i++) best_Sum += a[i];
u = K;
for(i = 1; i <= N; i++)
if(NR[i] >= K)
{
if(!GASIT)
{
GASIT = true;
best_Sum = best[i];
u = i;
}
else if(best_Sum < best[i])
{
best_Sum = best[i];
u = i;
}
}
int S = 0;
for(i = u; i >= 1; i--)
{
S += a[i];
if(S == best_Sum) p = i;
}
out << p << " " << u << " " << best_Sum;
return 0;
}