/* FILE: intervalSumSlow.cpp last change: 23-July-2012 author: Romeo Rizzi * a solver for problem 1 (IntervalSum) in the 23-07-2012 exam in Algorithms * a slow (quadratic) solver which computes the value of each possible feasible solution, employed for tuning the scores * at least it is not cubic since it avoids recomputing each value separately from scratch * here, this spearing from the cubic trivial solution is achieved by employing a prefix sum vector * this appears to be a simplest/safest possible code, thus useful for assessing correctness by comparisons of the outputs. */ // #include // NOTA: ho commentato questa riga per essere sicuro di non aver lasciato operazioni di input/output di debug nella fretta di consegnare, se compila cosi' non ci sono ed io non perdo stupidamente i miei punti-esame. #include #include #include using namespace std; const int MAX_N = 1000000; int n, k, vect[MAX_N]; int sum_of_the_first[MAX_N +1]; // sum_of_the_first[i] stores the sum of the first i elements int main() { sum_of_the_first[0] = 0; ifstream fin("input.txt"); assert(fin); fin >> n >> k; for(int i = 0; i < n; i++) { fin >> vect[i]; sum_of_the_first[i+1] = sum_of_the_first[i] + vect[i]; } fin.close(); int best_so_far = sum_of_the_first[k]; for(int first = 0; first+k-1 < n; first++ ) for(int last = first+k-1; last < n; last++ ) best_so_far = max( best_so_far, sum_of_the_first[last+1] - sum_of_the_first[first]); ofstream fout("output.txt"); assert(fout); fout << best_so_far; fout.close(); return 0; }