Max sum of 3x3


Submit solution


Points:100 (partial)
Time limit:0.5s
Java1.5s
Memory limit:64M
Java64M
Author:

Tags
Arrays
Difficulty
Easy

Allowed languages
C#, java, JavaScript

Write a program that reads a rectangular matrix of size N x M and finds in it the square 3 x 3 that has maximal sum of its elements. Print that sum.

Input

  • On the first line you will receive the numbers N and M separated by a single space
  • On the next N lines there will be M numbers separated with spaces - the elements of the matrix

Output

  • Print the maximal sum of 3 x 3 square

Constraints

  • 3 <= N, M <= 1024
  • Numbers in the matrix will be in the interval [ -1000, 1000 ]

Sample tests

Input Output
3 3
4 3 5
2 6 4
8 2 7
41
5 5
1 1 3 3 5
-6 -7 2 -3 -1
3 0 -4 5 9
7 -7 0 1 0
-7 -6 -4 -4 9
19

Comments


  • 0
    jackojelev
     commented on Dec. 9, 2018 edited

    Каква е разликата между това:

    for (int i = 0; i < n; i++)
            {
                inp[i] = Console.ReadLine();
            }
    
            for (int i = 0; i < n; i++)
            {
                matrix[i] = inp[i].Split(' ').Select(int.Parse).ToArray();
    
            }

    и това:

     for (int i = 0; i < n; i++)
            {
                matrix[i] = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            }

    при първото не минава 7,8 и 10 тест, но нямам проблем с 12 при Int16.


  • 1
    3akobah
     commented on Aug. 4, 2018 edit 6

    За колегите, които се чудят защо не им излизат два от тестовете на Java, каквото и да правят, но виждат, че все пак има хора, които са успели да се вместят във времето.

    За 0.5сек, колкото е времето отпуснато за тази задача, тя не може да бъде решена само с обичайните инструменти предоставени Ви от езика, защото I/O на конзолата е бавен и ще Ви трябва една по-сериозна подготовка(говоря за класове като StringTokenizer), за да успеете или ще трябва да преписвате код от хора, занимаващи се със състезателна Java.


  • 1
    jivko_hinev90
     commented on June 5, 2018

    Сложете 1 секунда на джава :)


  • 0
    ygabygabg
     commented on March 23, 2018

    Eхаааааа тоя последния кейс кърти! Разлика между 11 и 12 кейс е невероятна :О Работата с тия матрици е изключително "забавна"...
    Test case #11: AC [0.032s, 19.83 MB] (1/1)
    Test case #12: TLE [>0.500s, 46.57 MB] (0/1)


  • 0
    ygabygabg
     commented on March 14, 2018 edit 3

    Здравейте, някой може ли да ми каже защо на втория тест излиза 19 ? Нали уш събираме всички елементи от матрицата ? матрицата е 5х5 ред 1, 1 + 1 + 3 + 3 + 5 = 13 , ред 2, (-6)+ (-7)+ 2 + (-3)+ (-1) = -15, ред 3, 3 + 0 + (-4)+ 5 + 9 = 13, ред 4, 7 + (-7) + 0 + 1 + 0 = 1 ред 5, (-7)+ (-6)+ (-4)+ (-4)+ 9= -12 от тук следва 13 + (-15) + 13 + 1 +(-12)= 0 как тогава е посочен верен отговор 19?! Споделете какво не съм разбрал моля.

    ЕДИТ - ох ... ако матрицата е по голяма от 3х3 търсим най голямата сума 3х3 която се получава от голямата матрица? така ли излиза ?


  • 0
    rilabg
     commented on March 13, 2018 edit 5

    за C# може ли да се вдигне малко времето? Test case #12: TLE [0.500s, 45.12 MB] (0/1) Your output (clipped) 7347


    • 2
      adriyanmihaylov
       commented on March 13, 2018

      Има начин да ти мине решението като не използваш директен Parse метод. Разгледай тези методи - с малко допълнение за отрицателните числа си готов.


      • 0
        ygabygabg
         commented on March 23, 2018

        Здравейте, кое по точно не трябва да е "Parse" ? Четенето на редовете на матрицата или като цяло не трябва да има "Parse" ?


        • 0
          adriyanmihaylov
           commented on March 24, 2018

          Самото четене на входа - time limit-а не е достатъчен ако използваш parse методите на c#. Виж линка от предишния ми коментар,за преобразуване от string към integer


  • 0
    iordanbalt
     commented on Feb. 15, 2018 edit 3

    Да времето май е малко


  • 2
    markov.r
     commented on Feb. 7, 2018

    И аз оставам с впечатление, че времето е малко за Джава. За момента не виждам как да избягам от двете двойки вложени цикли.


    • 0
      k.zahariew
       commented on Feb. 20, 2018 edit 2

      Може да се реши с цикъл в цикъл :)


      • 0
        markov.r
         commented on Feb. 20, 2018 edited

        Тоест само една двойка вложени цикли? Колкото и да напрягам могъщата си мисъл не виждам как хем да прочета входа, хем да проверя и сумите в една двойка вложени цикли.


        • 0
          k.zahariew
           commented on Feb. 20, 2018 edited

          Ааа, не, не говоря за инпута :Д- само за решението ми, което е O(m*n). Вчера още не ми даваше, но сега ти погледнах последното 8/10 решение, което е същото като моето, само дето не ползвам шорт. Не знам, може би разликата идва от метода ни за четене на инпут. Докато е по-малък сме с равни времена, но предполагам, на нещо от сорта на 1000 по 1000 числа може би дава разлика.


          • 0
            markov.r
             commented on Feb. 20, 2018 edited

            Пробвах няколко начина, но не мога да се вместя в лимита.

            Със Scanner инпута става на един ред - input[i][j] = Short.valueOf(sc.next()); , но работи още по-бавно.

            С Buff. reader по-просто от това не мога да го докарам:

                for (int i = 0; i < n; i++) 
                {
                    String [] strIn = in.readLine().split(" ");
                    for (int j = 0; j < m; j++) 
                    {
                        input[i][j] = Short.parseShort(strIn[j]);
                    }
                }

            • 0
              k.zahariew
               commented on Feb. 20, 2018

              И аз сега пробвах и с BufferedReader, както и с BufferedRedaer + StringTokenizer и е бавно на същите два тесткейса като при теб. Май с тоя тайм лимит става само с "моя" къстъм риидър клас.


              • 0
                markov.r
                 commented on Feb. 20, 2018

                Нещо като т.4 от този линк ли ползваш?


                • 0
                  k.zahariew
                   commented on Feb. 20, 2018 edit 2

                  Не, принципно можеш просто да ми видиш кода на някоя задача, дето сме решили и двамата :Д Пратих ти приятелство във форума, приеми го, че иначе не мога да ти пратя съобщение, като гледам. П.П Всъщност да, подобно е.


                  • 0
                    markov.r
                     commented on Feb. 20, 2018

                    Видях класа, който ползваш, но нещо и с него не постигам голям напредък..

                    Във всеки случай няма да е излишно да се вдигне лимита за Java.


                    • 0
                      k.zahariew
                       commented on Feb. 20, 2018

                      Виж си съобщенията във форума, там ще ти обясня, да не спамим тук.


  • 1
    dyanakie
     commented on Jan. 28, 2018

    Каквото и да правя не мога да се включа в това време.Сменям с bufferedreader scanner-а но 3 опита пак TLE.Някакви други идеи да подобря скоростта?