Pagini recente » Cod sursa (job #565853) | Cod sursa (job #1073255) | Cod sursa (job #430924)
Cod sursa(job #430924)
#include <fstream>
#include <climits>
using namespace std;
int N,K,v[50000];
int structura[50000],structura2[50000],sume[50000],prev[50000];
void read_data();
void solve();
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;
}
}
for (int i = 1 ; i <= N - K + 1; ++i)
{
int sum = 0, j;
for (j = i ; j <= i + K - 1 ; ++j)
{
sum = sum + v[j];
}
j--;
sume[j] = sum;
}
int start = 0,max = INT_MIN,last;
for (int i = K ; i <= N ;++i)
{
structura[i] = sume[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;
}