Cod sursa(job #1321265)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 18 ianuarie 2015 22:10:53
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>

using namespace std;

#define MAX_LEN 50001
#define inFile "secventa2.in"
#define outFile "secventa2.out"

int s[MAX_LEN];

int main() {
    ifstream in(inFile);
    ofstream out(outFile);
    
    int N, K, i, iMin, iStart, iEnd, elem, min_so_far, best;
    
    in >> N >> K;
    for(i = 1; i <= N; i++) {
        in >> elem;
        s[i] = s[i-1] + elem;
    }
    
    min_so_far = 0; best = -(1<<30); iMin = 1;
    for(i = K; i <= N; i++) {
        
        if(s[i-K] < min_so_far) {
            min_so_far = s[i-K];
            iMin = i-K+1;
        }
        
        elem = s[i] - min_so_far;
        
        if(elem > best) {
            best = elem;
            iStart = iMin;
            iEnd = i;
        }
    }
    
    out << iStart << " " << iEnd << " " << best;
    
    return 0;
}