#include #include #include using namespace std; //variabili globali long n=0; long m=0; long s=0; const int MAX_N = 1000000; //lunghezza array int pfx[MAX_N]; //array delle somme prefisse //inizializza l'array void init() { for(int i=0; i< 1000000; i++) pfx[i]=0; } int main(){ ifstream fin("input.txt"); assert(fin); ofstream fout("output.txt"); assert(fout); init(); int value; int medium; int minimo; int massimo; int to_find; bool found; fin >> m >> n; fin >> pfx[0]; if( pfx[0] == m ) { // ho trovato gia' un M s++; } bool a =false; for(int i = 1; i < n; i++) { fin >> value; pfx[i] = value + pfx[i-1]; //calcolo le somme prefisse if(pfx[i] > m) { to_find = pfx[i] - m; //devo trovare l'elemento che differisce di M dall'elemento attuale found = false; minimo = 0; massimo = i; // elemento attuale //cerco in modo dicotomico per trovare piu' in fretta l'elemento che differisce di M dall'elemento attuale //ogni volta dimezzo lo spazio delle ricerche da effettuare while( !found && minimo <= massimo ) { medium = (minimo + massimo) / 2; if(pfx[medium] == to_find) { s++; //elemento cercato trovato, incremento il contatore found = true; } else if(pfx[medium] < to_find) minimo = medium +1; //cerco in un intervallo piu' stretto else massimo = medium -1; //cerco in un intervallo piu largo } if(found) { for(int l=medium +1; pfx[l] == pfx[medium]; l++) { s++; // ogni zero presente nell'array di input aumenta il numero di piante che danno come somma M } for(int l=medium -1; pfx[l] == pfx[medium]; l--) { s++; //uguale, ma fatto a sinistra } } } else if(pfx[i] == m) //la somma da '0' a 'i' e' uguale a M { s++; for(int l=i-1; pfx[l] == pfx[i] && pfx[l] == value && l >= 0; l--) { s++; } } } fout << s; fin.close(); fout.close(); return 0; }