Pagini recente » Cod sursa (job #2393646) | Cod sursa (job #2490852) | Cod sursa (job #2788142) | Cod sursa (job #3246486) | Cod sursa (job #3214024)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <unordered_map>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int maxn = 1e6+5, inf = 0x3f3f3f3f;
int a[maxn], maxim;
unordered_map <int, int> fr;
int main()
{
// for(auto u : fr) {
// cout << u.first << ' ' << u.second << '\n';
// }
int t, n, i, k, maxim = -inf, stmax, drmax;
fin >> n >> k;
for(i = 1; i <= n; i ++) {
fin >> a[i];
}
int st = 1, dr = k;
int s = 0;
for(i = 1; i <= k; i ++)
s += a[i];
if(s > maxim)
{
maxim = s;
stmax = st;
drmax = dr;
}
int s1 = 0;
while(dr < n) {
dr ++;
s += a[dr];
s1 += a[dr-k];
if(s1 < 0) {
st = dr - k + 1;
s -= s1;
s1 = 0;
}
if(s > maxim)
{
maxim = s;
stmax = st;
drmax = dr;
}
}
fout << stmax << ' ' << drmax << ' ' << maxim << '\n';
return 0;
}
/*
5
10
1 4 7 4 2 4 7 3 2 3
8
1 2 4 1 5 3 1 2
10
6 8 9 1 8 5 4 6 3 2
6
1 1 1 2 2 2
12
1 5 8 3 2 5 7 4 9 5 7 4
*/
//n=8 k=3
//1 -2 2 -4 1 2 2 2
// st dr
//s = -2
// sk = -1
//s1 = -1