Pagini recente » Cod sursa (job #312914) | Cod sursa (job #3036731) | Cod sursa (job #2866475) | Cod sursa (job #2950659) | Cod sursa (job #430931)
Cod sursa(job #430931)
#include <fstream>
#include <climits>
using namespace std;
int N,K,v[50000];
int structura[50000],structura2[50000],prev[50000];
void read_data();
void solve();
int sum(int i);
int main()
{
read_data();
solve();
return 0;
}
void read_data()
{
ifstream f("secv2.in");
f >> N >> K;
for (int i = 1 ; i <= N ; ++i)
f >> v[i];
f.close();
}
void solve()
{
ofstream g("secv2.out");
structura2[1] = v[1];
for (int k = 2; k <= N ; ++k)
{
if (structura2[k - 1] > 0)
{
structura2[k] = structura2[k - 1] + v[k];
prev[k] = prev[k - 1];
}
else
{
structura2[k] = v[k];
prev[k] = k;
}
}
int start = 0,max = INT_MIN,last;
for (int i = K ; i <= N ;++i)
{
structura[i] = sum(i);
if (structura2[i - K] > 0)
{
structura[i] += structura2[i - K];
if (structura[i] > max)
{
max = structura[i];
start = prev[structura2[i - K]];
last = i;
}
}
else if (structura[i] > max)
{
max = structura[i];
start = i - K + 1;
last = i;
}
}
for (int i = K ; i <= N ; ++i)
if (structura[i] > max)
max = structura[i];
if (!start)
start++;
g << start << " " << last << " " << max << endl;
}
int sum(int i)
{
int value = 0;
for (int k = i - K + 1; k <= i ; ++k)
{
value = value + v[k];
}
return value;
}