Cod sursa(job #2022568)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 16 septembrie 2017 18:57:09
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50000 +10;
using ll= long long;

ll v[maxn] = {};
array<ll, 2> d[maxn] = {};

int main(){
    ifstream f("secv2.in");
    ofstream g("secv2.out");
    ll n, k;
    f >> n >> k;
    for(ll i = 1; i <= n; ++i) f >> v[i];

    for(ll i = 1; i <= n; ++i){
        d[i] = max(d[i-1], array<ll, 2> { 0, i });
        d[i][0] += v[i]; }

    ll sum = 0;
    for(ll i = 1; i <= k; ++i) sum += v[i];

    array<ll, 3> rez = {sum, 1, k};
    for(ll i = k; i <= n; ++i, sum += v[i], sum -= v[i-k])
        rez = max(rez, array<ll, 3> { sum + d[i-k][0], d[i-k][1], i});

    g << rez[1] << ' '<< rez[2] << ' '<< rez[0] << endl;
    return 0; }