Cod sursa(job #2911223)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 27 iunie 2022 17:30:48
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>

#define inf 0x3f3f3f3f

using namespace std;

ifstream cin("secv2.in");
ofstream cout("secv2.out");

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> s(n);
    cin >> s[0];
    for(int i = 1; i < n; i++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    vector<int> dp(n), l(n);
    dp[k - 1] = s[k - 1];
    l[k - 1] = 0;
    int maxi = k - 1;
    for(int i = k; i < n; i++)
    {
        dp[i] = s[i] - s[i - k];
        l[i] = i - k + 1;
        if(dp[maxi] + s[i] - s[maxi] > dp[i])
        {
            dp[i] = dp[maxi] + s[i] - s[maxi];
            l[i] = l[maxi];
        }
        if(dp[maxi] - s[maxi] < dp[i] - s[i])
            maxi = i;
    }

    maxi = k - 1;
    for(int i = k; i < n; i++)
        if(dp[i] > dp[maxi])
            maxi = i;
    cout << l[maxi] + 1 << ' ' << maxi + 1 << ' ' << dp[maxi] << '\n';
}