250252026-02-17 13:55:31Leventusz09Maximális összegű útcpp17Wrong answer 5/100201ms6268 KiB
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long

#define IC for(int c=0; c<9; 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){
                    LN[c] = 0;
                    if(C[0][0] == c) LN[c] = A[0][0];
                    LR[0][c] = LN[c];
                }else
                if(i == 0){
                    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(lu < 0 && ll < 0){
                        if(C[i][j] == c){
                            LN[c] = A[i][j];
                        }else{
                            LN[c] = max(lu, ll) + A[i][j];
                        }
                    //}else LN[c] = C[i][j] == c ? max(lu, ll) + A[i][j] : 0;
                    }else if(lu == 0 && ll == 0){
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }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
                    cout << "D" << i <<" " << j <<" "<<c<< endl;
                    #endif
                }
            }
        }

        #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
2Accepted1ms508 KiB
subtask20/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms544 KiB
7Wrong answer1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms544 KiB
12Wrong answer1ms316 KiB
13Accepted1ms536 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer1ms316 KiB
22Wrong answer2ms316 KiB
23Wrong answer1ms316 KiB
24Accepted2ms404 KiB
25Accepted2ms408 KiB
26Accepted2ms408 KiB
27Wrong answer2ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms544 KiB
32Wrong answer1ms316 KiB
33Accepted1ms536 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Wrong answer1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer2ms316 KiB
43Wrong answer1ms316 KiB
44Accepted2ms404 KiB
45Accepted2ms408 KiB
46Accepted2ms408 KiB
47Wrong answer2ms316 KiB
48Accepted6ms1136 KiB
49Accepted6ms820 KiB
50Accepted6ms820 KiB
51Accepted6ms824 KiB
52Accepted6ms820 KiB
53Accepted6ms928 KiB
54Wrong answer6ms836 KiB
55Wrong answer6ms820 KiB
56Wrong answer8ms728 KiB
57Wrong answer8ms800 KiB
58Accepted8ms748 KiB
59Accepted8ms956 KiB
60Wrong answer8ms948 KiB
61Wrong answer8ms820 KiB
subtask55/5
62Accepted1ms372 KiB
63Accepted1ms316 KiB
64Accepted109ms6268 KiB
65Accepted108ms6220 KiB
66Accepted174ms6056 KiB
67Accepted165ms5688 KiB
68Accepted182ms6196 KiB
subtask60/12
69Wrong answer2ms316 KiB
70Accepted1ms508 KiB
71Accepted111ms6212 KiB
72Accepted112ms6196 KiB
73Accepted177ms5940 KiB
74Accepted165ms5680 KiB
75Accepted182ms6196 KiB
subtask70/54
76Accepted1ms500 KiB
77Accepted1ms500 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms544 KiB
82Wrong answer1ms316 KiB
83Accepted1ms536 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer1ms316 KiB
92Wrong answer2ms316 KiB
93Wrong answer1ms316 KiB
94Accepted2ms404 KiB
95Accepted2ms408 KiB
96Accepted2ms408 KiB
97Wrong answer2ms316 KiB
98Accepted6ms1136 KiB
99Accepted6ms820 KiB
100Accepted6ms820 KiB
101Accepted6ms824 KiB
102Accepted6ms820 KiB
103Accepted6ms928 KiB
104Wrong answer6ms836 KiB
105Wrong answer6ms820 KiB
106Wrong answer8ms728 KiB
107Wrong answer8ms800 KiB
108Accepted8ms748 KiB
109Accepted8ms956 KiB
110Wrong answer8ms948 KiB
111Wrong answer8ms820 KiB
112Accepted1ms372 KiB
113Accepted1ms316 KiB
114Accepted109ms6268 KiB
115Accepted108ms6220 KiB
116Accepted174ms6056 KiB
117Accepted165ms5688 KiB
118Accepted182ms6196 KiB
119Wrong answer2ms316 KiB
120Accepted1ms508 KiB
121Accepted111ms6212 KiB
122Accepted112ms6196 KiB
123Accepted177ms5940 KiB
124Accepted165ms5680 KiB
125Accepted182ms6196 KiB
126Wrong answer1ms316 KiB
127Wrong answer1ms316 KiB
128Wrong answer128ms6068 KiB
129Wrong answer128ms6196 KiB
130Wrong answer193ms6080 KiB
131Wrong answer180ms5556 KiB
132Accepted185ms6196 KiB
133Accepted187ms6028 KiB
134Wrong answer190ms6196 KiB
135Wrong answer192ms6196 KiB
136Wrong answer201ms6196 KiB