Cod sursa(job #2825029)

Utilizator DordeDorde Matei Dorde Data 3 ianuarie 2022 21:19:27
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n , k , v[50001] , s;
priority_queue<pair<int , int>> q;
int main()
{
    fin >> n >> k;
    q.push(mp(0 , 0));
    for(int i = 1 ; i <= n ; ++ i){
        fin >> v[i];
        s += v[i];
        v[i] += v[i - 1];
        q.push(mp(-s , i));
    }
    int ans = -(1 << 30) , l , r;
    for(int i = n ; i >= k ; -- i){
        while(!q.empty() && i - q.top().second < k)
            q.pop();
        if(v[i] + q.top().first > ans){
            ans = v[i] + q.top().first;
            l = q.top().second + 1;
            r = i;
        }
    }
    fout << l << ' ' << r << ' ' << ans;
    return 0;
}