Cod sursa(job #1771344)

Utilizator Moise_AndreiMoise Andrei Moise_Andrei Data 5 octombrie 2016 15:08:39
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
int c[50005], t[50005], v[50005];
int mx = 0, d = 0, sum = 0;
int main()
{
    int n, k;
    in >> n >> k;
    for(int i = 1; i <= n; i++){
        in >> v[i];
        t[i] = t[i-1] + v[i];
    }
    int mn = 1000000000;
    for(int i = k; i <= n; i++){
        mn = min(mn, t[i-k]);
        c[i] = max(c[i-1], t[i] - mn);
    }
    for(int i = 1; i <= n; i++)
        mx = max(mx, c[i]);
    for(int i = 1; i <= n; i++){
        if(c[i] == mx){
            d = i;
            break;
        }
    }
    int s = d;
    while(sum != mx || d - s + 1 < k){
        sum += v[s];
        s --;
    }
    out << s + 1 << " " << d << " " << mx;
    return 0;
}