251702026-02-18 10:39:32Leventusz09Maximális összegű útcpp17Wrong answer 9/100856ms6452 KiB
#include <iostream>
#include <vector>
#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 = A[0][0];
    int LR[M][500];
    int LN[500];
    for(int i=0; i<M; i++) IC LR[i][c] = 0;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            IC{
                if(i == 0 && j == 0){
                    // bal felső sarok
                    LN[c] = 0;
                    if(C[0][0] == c) LN[c] = A[0][0];
                    LR[0][c] = LN[c];
                }else
                if(i == 0){
                    // első sor
                    if(LN[c] > 0){
                        LN[c] += A[i][j];
                    }else{
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }
                    
                    LR[j][c] = LN[c];
                }
                else if(j==0){
                    if(LR[0][c] > 0){
                        LN[c] = LR[0][c] + A[i][j];
                    }else{
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }

                    LR[j][c] = LN[c];
                }else{
                    int lu = LR[j][c];
                    int ll = LN[c];
                    if(c != C[i][j] && lu == 0 && ll == 0){
                        LN[c] = 0;
                    }else{
                        if(c == C[i][j]){
                            LN[c] = max(0LL, max(lu, ll)) + A[i][j];                            
                        }else
                        LN[c] = max(lu, ll) + A[i][j];
                    }

                    LR[j][c] = LN[c];
                }
                if(C[i][j] == c) if(LN[c] > o) o = LN[c];
            }
        }

        #if DEBUG
        for(int i=0; i<M; i++){
            IC{
                cout << LR[i][c] << ".";
            }
            cout << " ";
        }
        cout << endl;
        #endif
    }

    cout << o << endl;
    
    return 0;
}

/*
3 3
1 1 1
1 1 1
1 1 1
1 2 3
4 5 6
7 8 9

*/
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask24/4
3Accepted1ms332 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms332 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms332 KiB
14Accepted1ms444 KiB
15Accepted3ms500 KiB
16Wrong answer1ms508 KiB
17Accepted1ms316 KiB
18Accepted4ms316 KiB
19Accepted1ms316 KiB
20Wrong answer1ms316 KiB
21Accepted4ms484 KiB
22Accepted4ms316 KiB
23Accepted4ms416 KiB
24Accepted4ms316 KiB
25Accepted4ms316 KiB
26Accepted4ms316 KiB
27Wrong answer4ms316 KiB
subtask40/18
28Accepted1ms332 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms332 KiB
34Accepted1ms444 KiB
35Accepted3ms500 KiB
36Wrong answer1ms508 KiB
37Accepted1ms316 KiB
38Accepted4ms316 KiB
39Accepted1ms316 KiB
40Wrong answer1ms316 KiB
41Accepted4ms484 KiB
42Accepted4ms316 KiB
43Accepted4ms416 KiB
44Accepted4ms316 KiB
45Accepted4ms316 KiB
46Accepted4ms316 KiB
47Wrong answer4ms316 KiB
48Accepted28ms948 KiB
49Accepted28ms820 KiB
50Accepted29ms944 KiB
51Accepted29ms944 KiB
52Accepted29ms940 KiB
53Accepted29ms820 KiB
54Accepted37ms944 KiB
55Accepted37ms836 KiB
56Wrong answer37ms1004 KiB
57Wrong answer37ms916 KiB
58Accepted32ms820 KiB
59Accepted32ms820 KiB
60Wrong answer32ms820 KiB
61Wrong answer39ms712 KiB
subtask55/5
62Accepted1ms512 KiB
63Accepted1ms316 KiB
64Accepted703ms6196 KiB
65Accepted703ms6196 KiB
66Accepted745ms5968 KiB
67Accepted699ms5460 KiB
68Accepted776ms6196 KiB
subtask60/12
69Wrong answer1ms316 KiB
70Accepted2ms316 KiB
71Accepted705ms6196 KiB
72Accepted704ms6452 KiB
73Accepted749ms5940 KiB
74Accepted703ms5680 KiB
75Accepted777ms6196 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms332 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms332 KiB
84Accepted1ms444 KiB
85Accepted3ms500 KiB
86Wrong answer1ms508 KiB
87Accepted1ms316 KiB
88Accepted4ms316 KiB
89Accepted1ms316 KiB
90Wrong answer1ms316 KiB
91Accepted4ms484 KiB
92Accepted4ms316 KiB
93Accepted4ms416 KiB
94Accepted4ms316 KiB
95Accepted4ms316 KiB
96Accepted4ms316 KiB
97Wrong answer4ms316 KiB
98Accepted28ms948 KiB
99Accepted28ms820 KiB
100Accepted29ms944 KiB
101Accepted29ms944 KiB
102Accepted29ms940 KiB
103Accepted29ms820 KiB
104Accepted37ms944 KiB
105Accepted37ms836 KiB
106Wrong answer37ms1004 KiB
107Wrong answer37ms916 KiB
108Accepted32ms820 KiB
109Accepted32ms820 KiB
110Wrong answer32ms820 KiB
111Wrong answer39ms712 KiB
112Accepted1ms512 KiB
113Accepted1ms316 KiB
114Accepted703ms6196 KiB
115Accepted703ms6196 KiB
116Accepted745ms5968 KiB
117Accepted699ms5460 KiB
118Accepted776ms6196 KiB
119Wrong answer1ms316 KiB
120Accepted2ms316 KiB
121Accepted705ms6196 KiB
122Accepted704ms6452 KiB
123Accepted749ms5940 KiB
124Accepted703ms5680 KiB
125Accepted777ms6196 KiB
126Accepted1ms316 KiB
127Wrong answer2ms508 KiB
128Wrong answer792ms6064 KiB
129Accepted787ms6248 KiB
130Wrong answer824ms5940 KiB
131Wrong answer774ms5596 KiB
132Accepted777ms6196 KiB
133Accepted777ms6196 KiB
134Wrong answer787ms6272 KiB
135Accepted794ms6064 KiB
136Accepted856ms6196 KiB