249902026-02-17 11:29:00Leventusz09Maximális összegű útcpp17Wrong answer 0/100587ms262144 KiB
#include <iostream>
#define DEBUG false

#define IC for(int c=0; c<500; c++)

using namespace std;

signed main(){
    int N, M;
    cin >> N >> M;

    int A[N][M];
    for(int i=0; i<N; i++) for(int j=0; j<M; j++) cin >> A[i][j];
    int C[N][M];
    for(int i=0; i<N; i++) for(int j=0; j<M; j++){
        cin >> C[i][j];
        C[i][j]--;
    }

    int L[N][M][500];
    int o=0;

    // bal felső sarok
    IC L[0][0][c] = 0;
    L[0][0][C[0][0]] = A[0][0];
    if(A[0][0] > o) o = A[0][0];

    // első sor
    for(int i=1; i<M; i++){
        IC{
            if(L[0][i-1][c] > 0 || C[0][i] == c){
                L[0][i][c] = L[0][i-1][c] + A[0][i];
            }else{
                L[0][i][c] = 0;
            }

            if(C[0][i] == c) if(L[0][i][c] > o) o = L[0][i][c];
        }
    }
    
    //első oszlop
    for(int i=1; i<N; i++){
        IC{
            if(L[i-1][0][c] > 0 || C[i][0] == c){
                L[i][0][c] = L[i-1][0][c] + A[i][0];
            }else{
                L[i][0][c] = 0;
            }

            if(C[i][0] == c) if(L[i][0][c] > o) o = L[i][0][c];
        }
    }

    // az összes többi
    for(int i=1; i<N; i++){
        for(int j=1; j<M; j++){
            IC{
                int cu = L[i-1][j][c];
                int cl = L[i][j-1][c];
                if(cu < 0 && cl < 0){
                    if(C[i][j] == c) L[i][j][c] = A[i][j];
                    else L[i][j][c] = max(cu, cl) + A[i][j];
                }
                else L[i][j][c] = max(cu, cl) + A[i][j];

                if(C[i][j] == c) if(L[i][j][c] > o) o = L[i][j][c];
            }
        }
    }
    #if DEBUG
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            IC{
                cout << L[i][j][c] << ".";
            }
            cout << "\t";
        }
        cout << "\n";
    }

    #endif
    cout << o << endl;
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/4
3Wrong answer1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Wrong answer1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms564 KiB
15Accepted4ms2100 KiB
16Accepted1ms508 KiB
17Accepted1ms564 KiB
18Accepted4ms2100 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms564 KiB
21Wrong answer4ms2100 KiB
22Wrong answer3ms1676 KiB
23Wrong answer4ms1844 KiB
24Wrong answer3ms2012 KiB
25Wrong answer4ms2004 KiB
26Wrong answer4ms2100 KiB
27Wrong answer4ms2100 KiB
subtask40/18
28Wrong answer1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms564 KiB
35Accepted4ms2100 KiB
36Accepted1ms508 KiB
37Accepted1ms564 KiB
38Accepted4ms2100 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms564 KiB
41Wrong answer4ms2100 KiB
42Wrong answer3ms1676 KiB
43Wrong answer4ms1844 KiB
44Wrong answer3ms2012 KiB
45Wrong answer4ms2004 KiB
46Wrong answer4ms2100 KiB
47Wrong answer4ms2100 KiB
48Wrong answer30ms19880 KiB
49Accepted28ms19988 KiB
50Accepted28ms19936 KiB
51Accepted30ms19936 KiB
52Wrong answer28ms20020 KiB
53Wrong answer28ms19820 KiB
54Wrong answer32ms20020 KiB
55Wrong answer28ms20032 KiB
56Wrong answer29ms18500 KiB
57Wrong answer30ms18740 KiB
58Wrong answer34ms20016 KiB
59Wrong answer34ms20020 KiB
60Wrong answer35ms19932 KiB
61Wrong answer32ms20024 KiB
subtask50/5
62Accepted2ms500 KiB
63Accepted2ms564 KiB
64Runtime error404ms262144 KiB
65Runtime error451ms262144 KiB
66Runtime error524ms262144 KiB
67Runtime error469ms262144 KiB
68Runtime error486ms262144 KiB
subtask60/12
69Accepted2ms316 KiB
70Accepted2ms564 KiB
71Runtime error402ms262144 KiB
72Runtime error407ms262144 KiB
73Runtime error522ms262144 KiB
74Runtime error512ms262144 KiB
75Runtime error483ms262144 KiB
subtask70/54
76Accepted1ms500 KiB
77Accepted1ms508 KiB
78Wrong answer1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms564 KiB
85Accepted4ms2100 KiB
86Accepted1ms508 KiB
87Accepted1ms564 KiB
88Accepted4ms2100 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms564 KiB
91Wrong answer4ms2100 KiB
92Wrong answer3ms1676 KiB
93Wrong answer4ms1844 KiB
94Wrong answer3ms2012 KiB
95Wrong answer4ms2004 KiB
96Wrong answer4ms2100 KiB
97Wrong answer4ms2100 KiB
98Wrong answer30ms19880 KiB
99Accepted28ms19988 KiB
100Accepted28ms19936 KiB
101Accepted30ms19936 KiB
102Wrong answer28ms20020 KiB
103Wrong answer28ms19820 KiB
104Wrong answer32ms20020 KiB
105Wrong answer28ms20032 KiB
106Wrong answer29ms18500 KiB
107Wrong answer30ms18740 KiB
108Wrong answer34ms20016 KiB
109Wrong answer34ms20020 KiB
110Wrong answer35ms19932 KiB
111Wrong answer32ms20024 KiB
112Accepted2ms500 KiB
113Accepted2ms564 KiB
114Runtime error404ms262144 KiB
115Runtime error451ms262144 KiB
116Runtime error524ms262144 KiB
117Runtime error469ms262144 KiB
118Runtime error486ms262144 KiB
119Accepted2ms316 KiB
120Accepted2ms564 KiB
121Runtime error402ms262144 KiB
122Runtime error407ms262144 KiB
123Runtime error522ms262144 KiB
124Runtime error512ms262144 KiB
125Runtime error483ms262144 KiB
126Wrong answer1ms508 KiB
127Wrong answer1ms564 KiB
128Runtime error421ms262144 KiB
129Runtime error416ms262144 KiB
130Runtime error587ms262144 KiB
131Runtime error584ms262144 KiB
132Runtime error476ms262144 KiB
133Runtime error485ms262144 KiB
134Runtime error537ms262144 KiB
135Runtime error545ms262144 KiB
136Runtime error550ms262144 KiB