Pagini recente » Cod sursa (job #942488) | Cod sursa (job #1604054)
#include <fstream>
#include <deque>
#include <algorithm>
#define NMAX 50001
using namespace std;
pair<int, int> AIB[NMAX];
int lIndex(int i)
{
return (i ^ (i - 1)) & i;
}
void process(int index, int value, int limit)
{
for (int i = index; i <= limit; i += lIndex(i))
{
if (value < AIB[i].second)
{
AIB[i] = make_pair(index, value);
}
}
}
pair<int, int> query(int index)
{
int i;
pair<int, int> result = make_pair(-1, 1 << 30);
for (i = index; i > 0; i -= lIndex(i))
{
if (AIB[i].second < result.second)
{
result.second = AIB[i].second;
result.first = AIB[i].first;
}
}
return result;
}
int main()
{
int n, k, v[NMAX], pSum[NMAX], i, smax = - (1<<30), start, end;
deque<int> d;
ifstream f("secv2.in");
f >> n >> k;
pSum[0] = 0;
for (i = 1; i <= n; i++)
{
f >> v[i];
pSum[i] = pSum[i - 1] + v[i];
process(i, pSum[i], n);
}
f.close();
for (i = k; i <= n; i++)
{
pair<int, int> min = query(i - k );
if (pSum[i] - min.second > smax)
{
smax = pSum[i] - min.second;
start = min.first + 1;
end = i;
}
}
ofstream g("secv2.out");
g << start << " " << end << " " << smax;
g.close();
return 0;
}