Plictisiți de Facebook și jocuri online, Diana și Jonny s-au gândit să joace un joc nou, care să necesite și mișcare în aer liber. Astfel, cei doi au desenat pe terenul de sport din liceu un dreptunghi pe care l-au împărțit cu N-1 linii orizontale și M-1 linii verticale în NxM pătrate identice, așezate pe N rânduri și M coloane, câte N pe fiecare rând și câte M pe fiecare coloană, ca în exemplu. Apoi, în interiorul fiecărui pătrat au scris câte un număr reprezentând valoarea pătratului respectiv în joc. După ce au terminat de scris cele NxM numere, Diana și Jonny au stabilit ca jocul să se desfășoare după următoarele reguli:

• Diana se poziționează în pătratul din colțul stânga-sus al dreptunghiului, iar Jonny se poziționează în pătratul din colțul dreapta-sus al dreptunghiului.
• Din pătratul în care se află, Diana se va deplasa făcând un pas în pătratul din dreapta de pe aceeași linie (dacă există) sau în pătratul situat pe linia următoare în aceeași coloană (dacă există), ca în desenul de mai jos.
  

  Exemplu

  joc2.in

  5 4
  90 25 70 33
  32 40 50 20
  43 80 55 70
  22 27 40 21
  80 45 78 34

  joc2.out

  1 452

  Explicație

  La finalul jocului, punctajul Dianei este 452, iar punctajul lui Jonny este 451. Câștigătorul jocului este Diana (:D). Astfel, fișierul de ieșire va conține pe prima linie numerele: 1 452. Trasee posibile de punctaj maxim pentru cei doi concurenți sunt următoarele:

  

  #include <bits/stdc++.h>
  using namespace std;
  
  ifstream cin("joc2.in");
  ofstream cout("joc2.out");
  
  int n , m , a[105][105] , b[105][105];
  
  int main()
  {
      cin >> n >> m;
  
      for(int i = 1 ; i <= n ; i++)
          for(int j = 1 ; j <= m ; j++)
          {
              cin >> a[i][j];
              b[i][j] = a[i][j];
          }
      for(int i = n ; i > 0 ; i--)
          for(int j = 1 ; j <= m ; j++)
              a[i][j] += max(a[i][j - 1] , a[i + 1][j]);
  
      for(int i = 1 ; i <= n ; i++)
          for(int j = 1 ; j <= m ; j++)
              b[i][j] += max(b[i - 1][j] , b[i][j - 1]);
  
      if(b[n][m] > a[1][m]) cout << "1 " << b[n][m];
      else if(b[n][m] < a[1][m]) cout << "2 " << a[1][m];
      else cout << "3 " << a[1][m];
  }

  Comentarii