Օլիմպիական ծրագրավորում

Անկյունագծային գումար

Քառակուսի մատրիցի անկյունագծային գումար կանվանենք գլխավոր և երկրորդական անկյունագծերի տարրերի գումարը։
Տրված է N × N չափի ամբողջ թվերից կազմած քառակուսի մատրից։ Հարկավոր է հաշվել այդ մատրիցի մեջ ընկած ամենամեծ անկյունագծային գումար ունեցող ենթամատրիցը։ Պետք է տպել այդ գումարը։
 
Մուտքի առաջին տողում տրված է մատրիցի N (1 ≤ N ≤ 100) չափը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են [-10000, 10000] միջակայքի N ամբողջ թվեր։
Ելքի միակ տողում պետք է արտածել մեկ թիվ՝ մեծագույն անկյունագծային գումարը։
Մուտք #1՝
2
3 -1
4  6


Ելք #1՝
12
 
Մուտք #2՝
4
0 -1 -2 -13
5  0  6 -2
0 -1  0 -1
0  0  7  0

Ելք #2՝
17
Այստեղ բացահայտ չենք հուշի թե ինչ ֆունկցիաներ է կարելի պատրաստել, բայց հնարավոր է բավական պարզեցնող ֆունկցիաներ սարքել, որից հետո խնդիրը ավելի կոկիկ լուծում կստանա։
 

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue