warrior98 Posted March 20, 2014 Report Share Posted March 20, 2014 Se da urmatoarea problema: RATB.Vreau sa stiu si eu o metoda mai eficienta decat cea pe care am postat-o mai jos, deoarece aceasta da TLE la 6 teste#include<fstream>#define Max 5001using namespace std;ifstream fin("ratb.in");ofstream fout("ratb.out");int long long n, k, i, j, l, s, smax = -4294967296, inc, sf;int short v[Max];int main() { fin >> n >> k; for (i = 1; i<=n; i++) { fin >> v[i]; } for (i = 1; i<=n-k+1; i++) { for (j = k; j<=n-i+1; j++) { for (l = i, s = 0; l<=i+j-1; l++) { s += v[l]; } if (s > smax) { smax = s; inc = i; sf = l-1; } } } fout << smax << endl << inc << " " << sf;}Am vazut ca se poate face si cu O(n) si cu O(n2), numai ca prima metoda se facea cu deque, ceea ce nu stiu sa fac, iar a doua metoda nu a fost postata. Quote Link to comment Share on other sites More sharing options...
alexandruth Posted March 20, 2014 Report Share Posted March 20, 2014 (edited) Penultimul rand "fout << smax << endl << inc << " " << sf;", transforma-l in "fout << smax << "\n" << inc << " " << sf;" pentru ca daca pui "endl" afecteaza buffer-ul si ii ia un timp enorm la executie.Edit: poti sa faci valorile intregi, sa nu te complici cu long long si cu define-ul ala (sau cu smax care e in long long). Restrictiile se aplica doar cand pui datele de intrare, adica daca iei un numar, sa se incadreze in specificatiile alea. Sa imi spui ce ti-a iesit, daca ti-a iesit. Edited March 20, 2014 by alexandruth Quote Link to comment Share on other sites More sharing options...
warrior98 Posted March 20, 2014 Author Report Share Posted March 20, 2014 (edited) @alexandruthStiu ca endl e mult mai lent decat "\n", dar la 3 endl nu se pierde multa performanta, diferenta se vede de la cateva mii de iterari.Prea complicat ... Am rezolvat-o mai usor, cu niste sume "istet" calculate. Complexitatea este O(n^2) si intra perfect ... Cu int nu imi dadea bine la un test, acum merge.LE: Am reusit sa descopar metoda de O(n2):#include<fstream>using namespace std;ifstream fin("ratb.in");ofstream fout("ratb.out");int n, k, v[5001], sv[5001], i, j, s, smax = -2147483648, inc, sf;int main() { fin >> n >> k; for (i = 1; i<=n; i++) { fin >> v[i]; sv[i] += sv[i-1] + v[i]; } for (i = 1; i<=n-k+1; i++) { for (j = i+k-1; j<=n; j++) { s = sv[j]-sv[i-1]; if (s > smax) { smax = s; inc = i; sf = j; } } } fout << smax << endl << inc << " " << sf; fin.close(); fout.close();} Edited March 21, 2014 by warrior98 Quote Link to comment Share on other sites More sharing options...