250232026-02-17 13:44:00Leventusz09Maximális összegű útcpp17Wrong answer 5/100196ms6220 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] = LR[j][c] = A[i][j];
                        }else{
                            LN[c] = LR[j][c] = max(lu, ll) + A[i][j];
                        }
                    }else LN[c] = LR[j][c] = C[i][j] == c ? max(lu, ll) + A[i][j] : 0;
                }
                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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask20/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Wrong answer1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Wrong answer1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms368 KiB
15Accepted2ms500 KiB
16Wrong answer1ms316 KiB
17Wrong answer1ms388 KiB
18Wrong answer1ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer1ms316 KiB
22Wrong answer1ms372 KiB
23Wrong answer2ms508 KiB
24Accepted2ms356 KiB
25Wrong answer2ms316 KiB
26Wrong answer2ms352 KiB
27Wrong answer2ms508 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Wrong answer1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms368 KiB
35Accepted2ms500 KiB
36Wrong answer1ms316 KiB
37Wrong answer1ms388 KiB
38Wrong answer1ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms372 KiB
43Wrong answer2ms508 KiB
44Accepted2ms356 KiB
45Wrong answer2ms316 KiB
46Wrong answer2ms352 KiB
47Wrong answer2ms508 KiB
48Accepted6ms1004 KiB
49Accepted6ms1004 KiB
50Wrong answer6ms824 KiB
51Wrong answer6ms820 KiB
52Wrong answer6ms940 KiB
53Wrong answer6ms820 KiB
54Wrong answer6ms772 KiB
55Wrong answer6ms736 KiB
56Wrong answer8ms820 KiB
57Wrong answer8ms916 KiB
58Accepted8ms820 KiB
59Wrong answer8ms928 KiB
60Wrong answer8ms1004 KiB
61Wrong answer8ms820 KiB
subtask55/5
62Accepted1ms316 KiB
63Accepted1ms500 KiB
64Accepted107ms6220 KiB
65Accepted108ms6084 KiB
66Accepted173ms5888 KiB
67Accepted162ms5672 KiB
68Accepted179ms6196 KiB
subtask60/12
69Wrong answer2ms316 KiB
70Wrong answer1ms316 KiB
71Wrong answer112ms6068 KiB
72Wrong answer111ms6052 KiB
73Wrong answer177ms5940 KiB
74Wrong answer167ms5592 KiB
75Wrong answer185ms6196 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms368 KiB
85Accepted2ms500 KiB
86Wrong answer1ms316 KiB
87Wrong answer1ms388 KiB
88Wrong answer1ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer1ms316 KiB
92Wrong answer1ms372 KiB
93Wrong answer2ms508 KiB
94Accepted2ms356 KiB
95Wrong answer2ms316 KiB
96Wrong answer2ms352 KiB
97Wrong answer2ms508 KiB
98Accepted6ms1004 KiB
99Accepted6ms1004 KiB
100Wrong answer6ms824 KiB
101Wrong answer6ms820 KiB
102Wrong answer6ms940 KiB
103Wrong answer6ms820 KiB
104Wrong answer6ms772 KiB
105Wrong answer6ms736 KiB
106Wrong answer8ms820 KiB
107Wrong answer8ms916 KiB
108Accepted8ms820 KiB
109Wrong answer8ms928 KiB
110Wrong answer8ms1004 KiB
111Wrong answer8ms820 KiB
112Accepted1ms316 KiB
113Accepted1ms500 KiB
114Accepted107ms6220 KiB
115Accepted108ms6084 KiB
116Accepted173ms5888 KiB
117Accepted162ms5672 KiB
118Accepted179ms6196 KiB
119Wrong answer2ms316 KiB
120Wrong answer1ms316 KiB
121Wrong answer112ms6068 KiB
122Wrong answer111ms6052 KiB
123Wrong answer177ms5940 KiB
124Wrong answer167ms5592 KiB
125Wrong answer185ms6196 KiB
126Wrong answer1ms500 KiB
127Wrong answer1ms508 KiB
128Wrong answer123ms6060 KiB
129Wrong answer125ms6180 KiB
130Wrong answer188ms5948 KiB
131Wrong answer177ms5624 KiB
132Wrong answer185ms6196 KiB
133Wrong answer188ms6196 KiB
134Wrong answer188ms6084 KiB
135Wrong answer188ms6076 KiB
136Wrong answer196ms6196 KiB