Cod sursa(job #3145971)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 17 august 2023 17:04:36
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

const int MAX_LENGTH = 50000;
const int MAX_SUM = 1250000000;

int main() {
    int numsLen, minLen;
    fin >> numsLen >> minLen;
    int nums[MAX_LENGTH + 1], sums[MAX_LENGTH + 1], st = 1, maxLen = 0, maxSt = 0, maxEnd = 0, maxSum = -MAX_SUM - 1;
    for (int i = 1; i <= numsLen; ++i) {
        fin >> nums[i];
        if (sums[i - 1] + nums[i] > nums[i]) {
            sums[i] = sums[i - 1] + nums[i];
        } else {
            sums[i] = nums[i];
            st = i;
        }
        if (i - st + 1 >= minLen && i - st + 1 > maxLen && sums[i] > maxSum) {
            maxSum = sums[i];
            maxSt = st;
            maxEnd = i;
            maxLen = i - st + 1;
        }
    }
    if (maxLen < minLen) {
        int sum = 0;
        for (int i = 1; i <= numsLen; ++i) {
            sum += nums[i];
            if (i > minLen) {
                sum -= nums[i - minLen];
            }
            if (sum > maxSum && i >= minLen) {
                maxSum = sum;
                maxSt = i - minLen + 1;
                maxEnd = i;
            }
        }
    }
    fout << maxSt << ' ' << maxEnd << ' ' << maxSum;
    return 0;
}
/*
 8 3
 0 -6 2 1 4 -1 3 -5
 =>
 3 7 9
 
 8 3
 1 2 3 -1 -1 1 2 3
 =>
 1 8 10
 
 8 3
 1 2 3 -5 -5 1 2 3
 =>
 1 3 6
 
 3 3
 -1 -2 -3
 =>
 1 3 -6
 
 4 3
 -1 -2 -3 1
 =>
 2 4 -4
 
 4 2
 -5 5 -5 5
 =>
 1 2 0
 */