Cod sursa(job #2957438)

Utilizator rapidu36Victor Manz rapidu36 Data 22 decembrie 2022 16:42:58
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

const int N = 50000;
const int INF = 2000000000;

int x[N+1];

int main()
{
    ifstream in("secv2.in");
    ofstream out("secv2.out");
    int n, k;
    int sc_i, sk_i = 0, smax = INF, st, dr, p_secv_c = 1;
    in >> n >> k;
    for (int i = 1; i <= k; i++)
    {
        in >> x[i];
        sk_i += x[i];
    }
    smax = sc_i = sk_i;
    st = 1;
    dr = k;
    for (int i = k + 1; i <= n; i++)
    {
        in >> x[i];
        ///actualizez sk_i
        sk_i += x[i] - x[i-k];
        if (sk_i > sc_i + x[i])///cea mai mare suma este cea cu exact k termeni
        {
            sc_i = sk_i;
            p_secv_c = i - k + 1;
        }
        else
        {
            sc_i += x[i];
        }
        if (sc_i > smax)
        {
            smax = sc_i;
            st = p_secv_c;
            dr = i;
        }
    }
    out << st << " " << dr << " " << smax << "\n";
    in.close();
    out.close();
    return 0;
}