Echipajul navei Enterprise, a descoperit pe planeta Marte, zona în care sunt amplasate b baze militare care adăpostesc navele de luptă ale marțienilor. Echipajul navei a reușit să cartografieze zona și a împărțit harta planetei în n x m zone de latură 1, dispuse pe n linii (numerotate de sus în jos de la 1 la n) și m coloane (numerotate de la stânga la dreapta de la 1 la m). Astfel fiecare zonă poate fi identificată prin numărul liniei și al coloanei pe care se află. În fiecare astfel de zonă se află o bază a marțienilor ce adăpostește un număr de nave. Căpitanul navei Enterprise, Jean-Luc Picard a elaborat o strategie de atac terestru a acestor baze militare.

Exemplu

nave.in

5 4 9
1 1 3
1 2 5
2 2 7
2 4 9
3 1 6
3 3 8 
4 1 1 
5 1 4
5 3 2

nave.out

29 4 2

Explicație

Harta zonei unde se găsesc bazele marțiene este:

Dacă nava Enterprise aterizează în zona situată pe linia 4 și coloana 2, va distruge un număr maxim de nave (29).

#include <bits/stdc++.h>

using namespace std;

ifstream cin("nave.in");
ofstream cout("nave.out");

int n , m , t , a[102][102] , x , y , val , maxi , lin , col;

int sum(int i , int j)
{
    int s = 0;
    int i1 = i , j1 = j;
    while(i1 >= 1 && j1 >= 1)
    {
        s += a[i1][j1];
        i1--;
        j1--;
    }
    int i2 = i , j2 = j;
    while(i2 >= 1 && j2 <= m)
    {
        s += a[i2][j2];
        i2--;
        j2++;
    }
    int i3 = i , j3 = j;
    while(i3 <= n && j3 >= 1)
    {
        s += a[i3][j3];
        i3++;
        j3--;
    }
    int i4 = i , j4 = j;
    while(i4 <= n && j4 <= m)
    {
        s += a[i4][j4];
        i4++;
        j4++;
    }
    return s;
}

int main()
{
    cin >> n >> m >>t;
    for(int i = 1 ; i <= t ; i++)
    {
        cin >> x >> y >> val;
        a[x][y] = val;
    }
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            if(a[i][j] == 0 && sum(i , j) >= maxi) maxi = sum(i , j) , lin = i , col = j;
    cout << maxi << " " << lin << " " << col;
}