Cerința

Epur iepurașul dorește să epureze niște apă folosind stațiile de epurare aflate pe o câmpie de formă pătrată având latură n. Epur iepurașul începe să epureze de la stația de epurare aflată la coordonatele (1, 1). După ce apa epurată la stația de epurare de pe coordonatele (x, y) e pură, Epur se va deplasa la o stație care are ambele coordonate mai mari sau egale cu coordonatele curente. Epur Iepurașul este obligat de Legea Epurării pentru Iepuri să epureze și la stația situată la coordonatele (n, n).

Se știe că fiecare stație de epurare oferă un grad de puritate număr întreg. Când Epur iepurașul își epurează apa la stația aflată la (x, y), gradul de puritate ale apei sale crește cu gradul oferit de stația de epurare folosită.

Ajutați-l pe Epur Iepurașul ca, epurând apa sa la stațiile de epurare să obțină un grad de puritate maxim.

Date de intrare

Fișierul de intrare epuras.in conține pe prima linie numărul n, iar pe următoarele n linii n numere naturale separate prin spații reprezentând gradul de puritate al apei oferit de fiecare stație de epurare.

Date de ieșire

Fișierul de ieșire epuras.out va conține pe prima linie numărul S, reprezentând gradul de puritate maxim.

Restricții și precizări

1 ≤ n ≤ 1.000
-10.000 ≤ gradele de puritate ≤ 10.000
rezultatul nu va depăși 32 de biți cu semn
fiecare stație de epurare poate fi folosită cel mult o dată

Exemplu

epuras.in

5
5 -2 3 4 6
3 -8 -10 8 4
2 5 2 3 4
-4 -2 -3 -1 -7
-7 -5 -6 -7 0

epuras.out

Explicație

(1, 1) -> (1, 3) -> (1, 4) -> (2, 4) -> (2, 5) -> (3, 5) -> (5, 5)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Epuras:

#include <fstream>
using namespace std;

ifstream fin ("epuras.in");
ofstream fout ("epuras.out");

const int N = 1005, oo = -1e9;

int n, d[N][N], a[N][N], MAX[N][N];

int main() {
    fin >> n;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            d[i][j] = MAX[i][j] = oo;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            fin >> a[i][j];
    d[1][1] = a[1][1];
    MAX[1][1] = d[1][1];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (!(i == 1 && j == 1)) {
                d[i][j] = max(MAX[i-1][j], MAX[i][j-1]) + a[i][j];
                MAX[i][j] = max(d[i][j], max(MAX[i-1][j], MAX[i][j-1]));
            }
    fout << d[n][n];
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1184 Epuras

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1184 Epuras de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1184 Epuras