Cod sursa(job #2814240)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 7 decembrie 2021 20:25:09
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("secv2.in");
ofstream fout ("secv2.out");

const int DIM = 50005;
long long smax[DIM], suma[DIM], last[DIM];
long long sol, crt;
int n, k, len, dist, st, dr;

int main (){
    fin>>n>>k>>suma[1];

    smax[1] = suma[1], last[1] = 1;
    for(int i=2; i<=n; i++){
        fin>>suma[i];


        if(smax[i-1] + suma[i] >= suma[i])
            smax[i] = smax[i-1] + suma[i], last[i] = last[i-1];
        else
            smax[i] = suma[i], last[i] = i;

        suma[i] += suma[i-1];
    }

    sol = -(1LL << 60);
    for(int i=k; i<=n; i++){
        crt = suma[i] - suma[i-k+1] + smax[i-k+1];
        len = i - last[i-k+1] + 1;

        if(crt > sol)
            sol = crt, dist = len, st = last[i-k+1], dr = i;
        else if(crt == sol && len > dist)
            dist = len, st = last[i-k+1], dr = i;
    }
    fout<<st<<" "<<dr<<" "<<sol;
    return 0;
}