Mai intai trebuie sa te autentifici.
Cod sursa(job #1099765)
| Utilizator | Data | 6 februarie 2014 11:56:06 | |
|---|---|---|---|
| Problema | Secventa 2 | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.9 kb |
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int Nmax = 50100;
const int oo = 0x3f3f3f3f;
long long N, K, S[Nmax], sol, st, dr;
deque <int> D;
int main()
{
fin >> N >> K;
for(int i = 1; i <= N; i++)
{
int x; fin >> x;
S[i] = S[i - 1] + x;
}
sol = S[K];
D.push_back(0); st = 1; dr = K;
for(int i = K + 1; i <= N; i++)
{
int V = S[i - K + 1];
if(sol < S[i] - S[D.front()])
{
sol = S[i] - S[D.front()];
st = D.front(); dr = i;
}
while(!D.empty() && S[D.back()] >= V)
D.pop_back();
D.push_back(i - K + 1);
}
if(!st) st = 1;
fout << st << ' ' << dr << ' ' << sol;
return 0;
}
