249912026-02-17 11:30:11Leventusz09Maximális összegű útcpp17Wrong answer 0/100469ms262144 KiB
#include <iostream>
#define DEBUG false
#define int long long

#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
1Accepted1ms512 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
14Accepted2ms564 KiB
15Accepted6ms3892 KiB
16Accepted1ms316 KiB
17Accepted1ms592 KiB
18Accepted4ms3892 KiB
19Wrong answer1ms540 KiB
20Wrong answer1ms564 KiB
21Wrong answer6ms3836 KiB
22Wrong answer4ms3200 KiB
23Wrong answer6ms3380 KiB
24Wrong answer4ms3892 KiB
25Accepted6ms3892 KiB
26Wrong answer6ms3892 KiB
27Wrong answer4ms3892 KiB
subtask40/18
28Wrong answer1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted2ms564 KiB
35Accepted6ms3892 KiB
36Accepted1ms316 KiB
37Accepted1ms592 KiB
38Accepted4ms3892 KiB
39Wrong answer1ms540 KiB
40Wrong answer1ms564 KiB
41Wrong answer6ms3836 KiB
42Wrong answer4ms3200 KiB
43Wrong answer6ms3380 KiB
44Wrong answer4ms3892 KiB
45Accepted6ms3892 KiB
46Wrong answer6ms3892 KiB
47Wrong answer4ms3892 KiB
48Wrong answer43ms39668 KiB
49Accepted50ms39476 KiB
50Accepted43ms39476 KiB
51Accepted50ms39468 KiB
52Wrong answer43ms39476 KiB
53Wrong answer43ms39480 KiB
54Wrong answer50ms39468 KiB
55Wrong answer50ms39548 KiB
56Wrong answer43ms36836 KiB
57Wrong answer43ms37324 KiB
58Wrong answer52ms39476 KiB
59Wrong answer52ms39476 KiB
60Wrong answer52ms39676 KiB
61Wrong answer46ms39476 KiB
subtask50/5
62Accepted1ms316 KiB
63Accepted2ms764 KiB
64Runtime error351ms262144 KiB
65Runtime error347ms262144 KiB
66Runtime error456ms262144 KiB
67Runtime error449ms262144 KiB
68Runtime error419ms262144 KiB
subtask60/12
69Accepted1ms540 KiB
70Accepted2ms756 KiB
71Runtime error351ms262144 KiB
72Runtime error395ms262144 KiB
73Runtime error462ms262144 KiB
74Runtime error402ms262144 KiB
75Runtime error421ms262144 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms512 KiB
78Wrong answer1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted2ms564 KiB
85Accepted6ms3892 KiB
86Accepted1ms316 KiB
87Accepted1ms592 KiB
88Accepted4ms3892 KiB
89Wrong answer1ms540 KiB
90Wrong answer1ms564 KiB
91Wrong answer6ms3836 KiB
92Wrong answer4ms3200 KiB
93Wrong answer6ms3380 KiB
94Wrong answer4ms3892 KiB
95Accepted6ms3892 KiB
96Wrong answer6ms3892 KiB
97Wrong answer4ms3892 KiB
98Wrong answer43ms39668 KiB
99Accepted50ms39476 KiB
100Accepted43ms39476 KiB
101Accepted50ms39468 KiB
102Wrong answer43ms39476 KiB
103Wrong answer43ms39480 KiB
104Wrong answer50ms39468 KiB
105Wrong answer50ms39548 KiB
106Wrong answer43ms36836 KiB
107Wrong answer43ms37324 KiB
108Wrong answer52ms39476 KiB
109Wrong answer52ms39476 KiB
110Wrong answer52ms39676 KiB
111Wrong answer46ms39476 KiB
112Accepted1ms316 KiB
113Accepted2ms764 KiB
114Runtime error351ms262144 KiB
115Runtime error347ms262144 KiB
116Runtime error456ms262144 KiB
117Runtime error449ms262144 KiB
118Runtime error419ms262144 KiB
119Accepted1ms540 KiB
120Accepted2ms756 KiB
121Runtime error351ms262144 KiB
122Runtime error395ms262144 KiB
123Runtime error462ms262144 KiB
124Runtime error402ms262144 KiB
125Runtime error421ms262144 KiB
126Wrong answer1ms316 KiB
127Wrong answer2ms564 KiB
128Runtime error414ms262144 KiB
129Runtime error368ms262144 KiB
130Runtime error423ms262144 KiB
131Runtime error465ms262144 KiB
132Runtime error462ms262144 KiB
133Runtime error414ms262144 KiB
134Runtime error469ms262144 KiB
135Runtime error423ms262144 KiB
136Runtime error425ms262144 KiB