Cod sursa(job #3214018)

Utilizator razviii237Uzum Razvan razviii237 Data 13 martie 2024 18:02:10
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <unordered_map>
using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int maxn = 1e6+5;
int a[maxn], maxim;
unordered_map <int, int> fr;
int main()
{
//    for(auto u : fr) {
//        cout << u.first << ' ' << u.second << '\n';
//    }
    int t, n, i, k, maxim = 0, stmax, drmax;

    fin >> n >> k;
    for(i = 1; i <= n; i ++) {
        fin >> a[i];
    }

    int st = 1, dr = k;
    int s = 0;
    for(i = 1; i <= k; i ++)
        s += a[i];
    if(s > maxim)
    {
        maxim = s;
        stmax = st;
        drmax = dr;
    }
    int s1 = 0;
    while(dr < n) {
        dr ++;
        s += a[dr];
        s1 += a[dr-k];
        if(s1 < 0) {
            st = dr - k + 1;
            s -= s1;
            s1 = 0;
        }
        if(s > maxim)
            {
                maxim = s;
                stmax = st;
                drmax = dr;
            }
    }
    fout << stmax << ' ' << drmax << ' ' << maxim << '\n';
    return 0;
}

/*
 5
 10
 1 4 7 4 2 4 7 3 2 3
 8
 1 2 4 1 5 3 1 2
 10
 6 8 9 1 8 5 4 6 3 2
 6
 1 1 1 2 2 2
 12
 1 5 8 3 2 5 7 4 9 5 7 4

 */


//n=8 k=3
//1 -2  2 -4 1 2 2 2
//      st   dr
//s = -2
//        sk = -1
//s1 = -1