Pagini recente » Cod sursa (job #1104878) | Cod sursa (job #671693) | Cod sursa (job #1523762) | Cod sursa (job #2753420) | Cod sursa (job #1443233)
#include <iostream>
#include <fstream>
#define N_MAX 50000
#define INF -1000000000
using namespace std;
struct suma
{
int s, l;
}sum[N_MAX];
int v[N_MAX], n, k;
void citire()
{
ifstream in("secv2.in");
in >> n >> k;
for(int i = 0; i < n; i++)
in >> v[i];
}
suma max_sum(int p)
{
int i = p, s_max = 0, s = 0, l = 0;
for(i = p; i < p + k; i++)
s_max += v[i];
l = i - p + 1;
s = s_max;
while(i < n)
{
s += v[i];
if(s > s_max)
{
s_max = s;
l = i - p + 1;
}
i++;
}
suma ss;
ss.s = s_max;
ss.l = l;
return ss;
}
void secv()
{
for(int i = 0; i < n; i++)
{
sum[i].s = INF;
}
int lo = 0, hi = 0, s = 0;
for(int l = k; l < n; l++)
{
lo = 0, hi = l + lo, s = 0;
for(int i = lo; i < hi; i++)
s += v[i];
if (s > sum[lo].s)
{
sum[lo].s = s;
sum[lo].l = l;
//cout << s << " " << l << " " << lo << endl;
}
//cout << s << " " << l << " " << lo << " " << v[lo-1] << " " << v[hi] << endl;
while(hi < n)
{
s -= v[lo++];
s += v[hi++];
//cout << s << " " << l << " " << lo << " " << v[lo-1] << " " << v[hi] << endl;
if(s > sum[lo].s)
{
sum[lo].s = s;
sum[lo].l = l;
}
}
}
ofstream out("secv2.out");
suma s_max = sum[0];
int p = 0;
for(int i = 0; i < n; i++)
{
if(sum[i].s > s_max.s)
{
s_max = sum[i];
p = i;
}
}
/*int p = 0;
suma s_max = sum[0];
ofstream out("secv2.out");
for(int i = 0; i < n; i++)
{
if(sum[i].s > s_max.s)
{
s_max = sum[i];
p = i;
}
}*/
out << p+1 << " " << s_max.l + p << " " << s_max.s;
}
int main()
{
citire();
secv();
return 0;
}