Cod sursa(job #1861953)

Utilizator vazanIonescu Victor Razvan vazan Data 29 ianuarie 2017 13:49:13
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
using namespace std;
typedef pair<int, int> pii;
const int inf = 2.0e+9;
inline void solve(const int n, const int k, ifstream &fin, ofstream &fout){
    int accum(0), cr, left_len(0), left_bound(0), maxim = -inf;
    pii *left = new pii[n], sol;
    left = new pii[n];
    left[0].first = 0;
    left[0].second = 0;
    for(int i(1); i <= n; ++i){
        fin >> cr;
        accum += cr;
        if(accum < left[left_len].first){
            left[++left_len].first = accum;
            left[left_len].second = i;
        }
        while(i - left[left_bound].second >= k && left_bound <= left_len){
            if(accum - left[left_bound].first > maxim){
                maxim = accum - left[left_bound].first;
                sol.first = left[left_bound].second + 1;
                sol.second = i;
            }
            ++left_bound;
        }
        if(left_bound)
            --left_bound;
    }
    fout << sol.first << ' ' << sol.second << ' ' << maxim << endl;
    return;
}


int main(){
    ifstream fin("secv2.in");
    ofstream fout("secv2.out");
    int n, k;
    fin >> n >> k;
    solve(n, k, fin, fout);
    return 0;
}