Cod sursa(job #2725901)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 19 martie 2021 20:23:22
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n, k, nr, v[50100], sp[50100], end_point[50100];
 
int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
		sp[i] = sp[i - 1] + v[i];
	}
 
	int suma = -1;
	for (int i = n; i >= 1; i--) {
		if (suma < 0)
			end_point[i] = i;
		else
			end_point[i] = end_point[i + 1];
		suma = max(v[i], suma + v[i]);
	}
 
	int suma_max = INT_MIN, in_max, sf_max;
	for (int i = 1; i <= n - k + 1; i++) {
		int sf = end_point[i + k - 1];
		int suma = sp[sf] - sp[i - 1];
 
		if (suma > suma_max) {
			suma_max = suma;
			in_max = i;
			sf_max = sf;
		}
	}
 
	fout << in_max << ' ' << sf_max << ' ' << suma_max;
    return 0;
}

/*#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
 
ifstream fin("secv2.in");
ofstream fout("secv2.out");
 
int main(){
    int n, sum = 0, best_sum = INT_MIN, index, start, finish, x, k, total_sum = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        total_sum += x;
        if (sum <= 0) {
            index = i;
            sum = 0;
        }
        sum += x;
        if (sum >= best_sum && i - index >= k) {
            start = index;
            finish = i;
            best_sum = sum;
        }
    }
    if (best_sum == INT_MIN) {
        cout << 1 << " " << n << " " << total_sum;
    }
    else {
        cout << start << " " << finish << " " << best_sum;
    }
    return 0;
}*/