Pagini recente » Cod sursa (job #904151) | Cod sursa (job #1250538) | Cod sursa (job #1664211) | Cod sursa (job #2498522) | Cod sursa (job #789880)
Cod sursa(job #789880)
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fi("secv2.in");
ofstream fo("secv2.out");
int N, K, *V;
int a, b, c = -(1 << 30);
void possible(int li, int ls, int sum)
{
if(sum > c)
a = li, b = ls, c = sum;
}
void write()
{
fo << a + 2 << " "
<< b + 1 << " "
<< c << endl;
}
void read()
{
fi >> N >> K;
V = new int[N];
int s = 0;
for(int i = 0; i < N; i++)
{
fi >> V[i];
s += V[i];
}
}
void naive()
{
for(int i = 0; i < N; i++)
{
for(int j = i + K - 1; j < N; j++)
{
int s = 0;
for(int k = i; k <= j; k++)
s += V[k];
possible(i, j, s);
}
}
}
void print(int *v, int n)
{
for(int i = 0; i < n; i++)
cout << v[i] << " ";
cout << endl;
}
int *KS;
void ksums()
{
KS = new int[N];
int s(0);
for(int i = 0; i < N; i++)
{
s += V[i];
KS[i] = s;
}
}
void update_mpm(int& m, int& pm, int newp)
{
if(KS[newp] < m)
{
m = KS[newp];
pm = newp;
}
}
void solve()
{
int m = 0;
int pm = -1;
for(int i = K - 1; i < N; i++)
{
possible(pm, i, KS[i] - m);
// cout << "C(" << i << ") = " << KS[i] - m << endl;
update_mpm(m, pm, i - K + 1);
}
}
void printbest()
{
cout << "BEST: "
<< a + 1 << " "
<< b + 1 << " "
<< c << endl;
}
int main(int argc, char *argv[])
{
read();
ksums();
// print(KS, N);
// naive();
solve();
write();
return 0;
}