Cod sursa(job #3003089)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 15 martie 2023 14:23:28
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<bits/stdc++.h>
#define y1 nefdi
#define DIM 1000001
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int v[DIM], sp[DIM];
int i, n, k, Max = -1e9, st, dr;
deque <int> d;
char c;
bool GetInt(int &x){
    if(c == -1)
        return false;
    while((c = getchar()) && c == ' ');
    if(c == -1)
        return false;
    int sign = (c == '-' ? -1 : 1);
    if(isdigit(c))
        x = c - '0';
    else x = 0;
    while((c = getchar()) && isdigit(c))
        x = x * 10 + c - '0';
    x *= sign;
    return true;
}
int main(){
    freopen("secv2.in", "r", stdin);
    GetInt(n);
    GetInt(k);
    for(i=1;i<=n;i++)
        GetInt(v[i]);
    for(i=1;i<=n;i++)
        sp[i] = v[i] + sp[i - 1];
    for(i=k;i<=n;i++){
        while(!d.empty() && sp[i]  - sp[i - k] >= sp[i] - sp[d.back()])
            d.pop_back();
        d.push_back(i - k);
        while(i - d.front() < k)
            d.pop_front();
        if(sp[i] - sp[d.front()] > Max){
            Max = sp[i] - sp[d.front()];
            st = d.front() + 1;
            dr = i;
        }
    }
    fout << st << " " << dr << " " << Max;
}