251812026-02-18 11:47:10Leventusz09Maximális összegű útcpp17Wrong answer 9/100857ms6284 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){
                    // első oszlop
                    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]){
                        LN[c] = max(0LL, max(lu, ll)) + A[i][j];
                    }else{
                        if(lu == 0 && ll == 0) LN[c] = 0;
                        else LN[c] = max(lu, ll) + A[i][j];
                    }
                    /*
                    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
2Accepted1ms500 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted4ms532 KiB
16Wrong answer1ms508 KiB
17Accepted1ms316 KiB
18Accepted3ms552 KiB
19Accepted1ms508 KiB
20Wrong answer2ms316 KiB
21Accepted4ms532 KiB
22Accepted4ms724 KiB
23Accepted4ms316 KiB
24Accepted4ms316 KiB
25Accepted4ms316 KiB
26Accepted4ms528 KiB
27Wrong answer4ms404 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted4ms532 KiB
36Wrong answer1ms508 KiB
37Accepted1ms316 KiB
38Accepted3ms552 KiB
39Accepted1ms508 KiB
40Wrong answer2ms316 KiB
41Accepted4ms532 KiB
42Accepted4ms724 KiB
43Accepted4ms316 KiB
44Accepted4ms316 KiB
45Accepted4ms316 KiB
46Accepted4ms528 KiB
47Wrong answer4ms404 KiB
48Accepted29ms1004 KiB
49Accepted29ms952 KiB
50Accepted29ms1008 KiB
51Accepted29ms948 KiB
52Accepted28ms820 KiB
53Accepted28ms1012 KiB
54Accepted37ms820 KiB
55Accepted37ms820 KiB
56Wrong answer37ms940 KiB
57Wrong answer37ms836 KiB
58Accepted32ms820 KiB
59Accepted32ms944 KiB
60Wrong answer32ms820 KiB
61Wrong answer39ms1012 KiB
subtask55/5
62Accepted2ms316 KiB
63Accepted2ms316 KiB
64Accepted703ms6196 KiB
65Accepted703ms6212 KiB
66Accepted745ms6048 KiB
67Accepted700ms5452 KiB
68Accepted777ms6208 KiB
subtask60/12
69Wrong answer2ms316 KiB
70Accepted1ms316 KiB
71Accepted704ms6196 KiB
72Accepted704ms6196 KiB
73Accepted746ms6004 KiB
74Accepted702ms5592 KiB
75Accepted777ms6204 KiB
subtask70/54
76Accepted1ms508 KiB
77Accepted1ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted4ms532 KiB
86Wrong answer1ms508 KiB
87Accepted1ms316 KiB
88Accepted3ms552 KiB
89Accepted1ms508 KiB
90Wrong answer2ms316 KiB
91Accepted4ms532 KiB
92Accepted4ms724 KiB
93Accepted4ms316 KiB
94Accepted4ms316 KiB
95Accepted4ms316 KiB
96Accepted4ms528 KiB
97Wrong answer4ms404 KiB
98Accepted29ms1004 KiB
99Accepted29ms952 KiB
100Accepted29ms1008 KiB
101Accepted29ms948 KiB
102Accepted28ms820 KiB
103Accepted28ms1012 KiB
104Accepted37ms820 KiB
105Accepted37ms820 KiB
106Wrong answer37ms940 KiB
107Wrong answer37ms836 KiB
108Accepted32ms820 KiB
109Accepted32ms944 KiB
110Wrong answer32ms820 KiB
111Wrong answer39ms1012 KiB
112Accepted2ms316 KiB
113Accepted2ms316 KiB
114Accepted703ms6196 KiB
115Accepted703ms6212 KiB
116Accepted745ms6048 KiB
117Accepted700ms5452 KiB
118Accepted777ms6208 KiB
119Wrong answer2ms316 KiB
120Accepted1ms316 KiB
121Accepted704ms6196 KiB
122Accepted704ms6196 KiB
123Accepted746ms6004 KiB
124Accepted702ms5592 KiB
125Accepted777ms6204 KiB
126Accepted1ms316 KiB
127Wrong answer2ms508 KiB
128Wrong answer791ms6268 KiB
129Accepted785ms6084 KiB
130Wrong answer824ms6072 KiB
131Wrong answer774ms5532 KiB
132Accepted777ms6108 KiB
133Accepted779ms6232 KiB
134Wrong answer787ms6056 KiB
135Accepted796ms6052 KiB
136Accepted857ms6284 KiB