Witam, mam takie zadanko, http://pl.spoj.com/problems/BAJTIOS1/ moj program podaje prawidłowe wyniki, ale jest zbyt wolny algorytm i cały czas dostaję przekroczono czas na spoj, moje pytanie brzmi jak go usprawnić i zoptymalizować aby działał szybciej ? Jakieś fast IO czy coś w tym stylu?
Mój kod programu wygląda następująco, mam w nim cztery pętle for i myślę, że również przez nie program działa dużo wolniej:
Proszę o jakieś wskazówki dla początkującego :)
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
/*
n - liczba dni pomiarow
m - liczba punktow pomiarowych
p - srednie zanieczyszczenie
q - liczba zapytan
a - pierwszy dzien okresu pomiarowego
b - ostatni dzien okresu pomiarowego
*/
int main() {
std::ios_base::sync_with_stdio(0);
int n;
int q, a, b;
double p, m, k;
double suma;
int liczba_dni_przekroczen = 0;
string number;
vector<double> srednie;
scanf("%d %lf %lf", &n, &m, &p);
k = 1 / m;
for(int index = 0; index < n; ++index) { // LOOP
suma = 0.0;
cin >> number;
while(cin.get() != '\n');
for(int index_punktow = 0; index_punktow < m; ++index_punktow) { // LOOP
string tmp = " ";
tmp[0] = number[index_punktow];
suma += atoi( tmp.c_str() );
}
srednie.push_back( suma * k ); // srednia pomiaru dla danego dnia ( mnozenie szybsze przez odwrotnosc m )
}
scanf("%d", &q);// liczba zapytan
for(int index = 0; index < q; ++index) { // LOOP
scanf("%d %d", &a, &b);
for(int i = a-1; i < b && i < srednie.size(); ++i) { // LOOP
if(srednie[i] > p) liczba_dni_przekroczen += 1;
}
printf("%d\n", liczba_dni_przekroczen);
}
return 0;
}