Cod sursa(job #848992)

Utilizator razvan.popaPopa Razvan razvan.popa Data 5 ianuarie 2013 22:58:46
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define infile "secv2.in"
#define outfile "secv2.out"
#define INF (1<<30)
#define nxt (*it)
#define nMax 50005
#define FOR(g)\
   for(vector<int>::iterator it=g.begin(); it!=g.end(); ++it)
using namespace std;

int DP[nMax];

int N, K;

int Sol = -INF, ii, jj;


void read(){
    ifstream f(infile);

    f >> N >> K;

    for(int i=1; i<=N; ++i){
        f >> DP[i];
        DP[i] += DP[i-1];
    }

    f.close();
}

void solve(){
    int idx = 0, minS = 0, iS = 1;

    for(int i=K; i<=N; ++i, ++idx){
        if(DP[idx] < minS){
            minS = DP[idx];
            iS = idx + 1;
        }

        if(DP[i] - minS > Sol){
            Sol = DP[i] - minS;
            ii = iS;
            jj = i;
        }
    }
}

void print(){
    ofstream g(outfile);

    g << ii << " " << jj << " " << Sol << '\n';

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}