Edilizia fantasiosa execution timed out a due

Aiuto
1

Nei soli test 027 e 029 ci mette più di 1 secondo ma nel resto dei test massimo 0.1, quale è il problema?

Codice :

#include<iostream>
#include<fstream>
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

int V[100000];

int main(){
	
	int N, K, min = 0, somma = 0;
	
	in >> N >> K;
	
	for(int i = 0; i < N; i ++) in >> V[i];
	
	for(int i = 0; i < (N - K) + 1; i ++){
		somma = 0;
		
		for(int j = i; j < K + i; j ++){
			somma += V[j];
		}
		
		if(i == 0) min = somma;
		
		if(somma < min) min = somma;
	}
	
	out << min;
}
2 Mi Piace
2

Questo è un classico problema di sliding window.

L’osservazione cruciale è: se conosci la somma da i a j allora per conoscere la somma da i+1 a j+1 non serve ricalcolarla da 0, in quanto puoi ricavare la somma da i+1 a j ed “aggiustare” quella.

Svolto nel modo corretto abbassa la complessità da O((n-k)k) a O(N)

2 Mi Piace
3

Giusto, risolto 100/100 thx

2 Mi Piace