Կապակցված վանդակներ
Մատրիցի վանդակների
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