Problema olimpiada

[warrior98]

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 5001

using 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(n²), numai ca prima metoda se facea cu deque, ceea ce nu stiu sa fac, iar a doua metoda nu a fost postata.

[alexandruth]

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

[warrior98]

@alexandruth

Stiu 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(n²):

#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