Կապակցված վանդակներ

Մատրիցի վանդակների S ենթաբազմությունը կանվանենք կապակցված, եթե գոյություն ունի այդ ենթաբազմությանը պատկանող ցանկացած վանդակից ցանկացած այլ վանդակ տանող ճանապարհ ։ Իսկ ճանապարհ ասելով, կհասկանանք վանդակների այնպիսի հաջորդականություն, որտեղ բոլոր երկու հարևան i=1…k-1, տարրերն ընդհանուր կողմ ունեն։
Տրված է N տողերից և M սյուներից կազմված A մատրիցը։ A մատրիցին պատկանող S կապակցված ենթաբազմության համար սահմանենք կշիռ հետևյալ կերպ․
Որտեղ |S|-ը ցույց է տալիս S ենթաբազմության տարրերի քանակը, իսկ A(t)-ն մատրից t տարրի արժեքն է։

Մուտքային տվյալներ

Առաջին տողում տրված են մատրից N և M (1 ≤ N, M ≤ 1000) չափերը։
Հաջոր N տողերից յուրաքանչուրում տրված են M ոչ բացասական ամբողջ թվեր՝ մատրիցի A[i][j] տարրերը։

Ելքային տվյալներ

Արտածեք մեկ թիվ՝ տրված մատրիցի բոլոր հնարավոր S կապակացված ենթաբազմություններից մեծագույն կշիռ ունեցողի weight(S) կշիռը։

Ենթախնդիրներ

  • Ենթախնդիր 0. Օրինակը (0 միավոր)
  • Ենթախնդիր 1. N = 1 (15 միավոր)
  • Ենթախնդիր 2. 1 ≤ N * M ≤ 20 (20 միավոր)
  • Ենթախնդիր 3. 1 ≤ N, M ≤ 50 (30 միավոր)
  • Ենթախնդիր 4. Լրացուցիչ սահմանափակումներ չկան (35 միավոր)։

Օրինակ

Մուտք
Ելք
2 3 2 3 4 5 8 5
3

Բացատրություն

Դիտարկենք {(0,0), (0,1), (1,1)} կապակցված ենթաբազմությունը կամ {(0,0), (1,0),(1,1)} կապակցված ենթաբազմությունը։ Նրանց երկուսի կշիռն էլ 3 է։ Ավելի մեծ կշռով կապակցված ենթաբազմություն այս օրինակում գոյություն չունի։
 
Աղբյուրը՝ Հանրապետական 2022
 

Constraints

Time limit: 0.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

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