Cod sursa(job #2846758)

Utilizator 100pCiornei Stefan 100p Data 9 februarie 2022 17:11:18
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("secv2.in","r",stdin);\
              freopen("secv2.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 1000000007
#define ll long long
#define SMAX 300
#define MAX 50000
#define pb push_back
#define add emplace_back
#define void inline void

using namespace std;
int n,v[MAX+5],sm[MAX+5],m;
vector<int> go[MAX+5];
int main()
{
    fastio
    FILES
    cin >> n >> m;
    for(int i = 1;i <= n; ++i)
        cin >> v[i],sm[i] += sm[i-1] + v[i];
    int best = sm[m],start = 1,endp = m;
    deque<pair<int,int>> dq;
    for(int i = 2;i <= m; ++i)
       go[i+m-1].add(i);
    dq.push_back(mp(best,1));
    for(int i = m + 1;i <= n; ++i)
    {
        for(auto j : go[i])
        {
            int x = sm[i] - sm[j-1];
            while(!dq.empty() && x > dq.back().first + sm[i] - sm[dq.back().second+m-1]) dq.pop_back();
            dq.push_back(mp(x,j));
        }
        go[i].clear();
        int sum = dq.front().first + sm[i] - sm[dq.front().second+m-1];
        if(sum > best) best = sum,start = dq.front().second,endp = i;
        go[i+m-1].add(i);
    }
    cout << start << ' ' << endp << ' ' << best;
}