251392026-02-18 08:45:05Leventusz09Maximális összegű útcpp17Wrong answer 9/100857ms6276 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){
                    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
1Accepted1ms532 KiB
2Accepted1ms316 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
13Accepted1ms512 KiB
14Accepted1ms508 KiB
15Accepted3ms512 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted3ms528 KiB
19Accepted1ms316 KiB
20Wrong answer1ms508 KiB
21Accepted4ms508 KiB
22Accepted4ms316 KiB
23Accepted4ms316 KiB
24Accepted4ms316 KiB
25Accepted3ms356 KiB
26Accepted3ms316 KiB
27Wrong answer4ms536 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms512 KiB
34Accepted1ms508 KiB
35Accepted3ms512 KiB
36Wrong answer1ms316 KiB
37Accepted1ms316 KiB
38Accepted3ms528 KiB
39Accepted1ms316 KiB
40Wrong answer1ms508 KiB
41Accepted4ms508 KiB
42Accepted4ms316 KiB
43Accepted4ms316 KiB
44Accepted4ms316 KiB
45Accepted3ms356 KiB
46Accepted3ms316 KiB
47Wrong answer4ms536 KiB
48Accepted25ms940 KiB
49Accepted25ms820 KiB
50Accepted25ms944 KiB
51Accepted25ms820 KiB
52Accepted26ms1148 KiB
53Accepted25ms1072 KiB
54Accepted37ms820 KiB
55Accepted37ms1052 KiB
56Wrong answer37ms820 KiB
57Wrong answer37ms820 KiB
58Accepted27ms944 KiB
59Accepted28ms820 KiB
60Wrong answer28ms820 KiB
61Wrong answer39ms960 KiB
subtask55/5
62Accepted1ms500 KiB
63Accepted2ms316 KiB
64Accepted582ms6192 KiB
65Accepted582ms6196 KiB
66Accepted630ms5940 KiB
67Accepted592ms5564 KiB
68Accepted654ms6196 KiB
subtask60/12
69Wrong answer2ms508 KiB
70Accepted2ms508 KiB
71Accepted583ms6200 KiB
72Accepted584ms6268 KiB
73Accepted633ms5964 KiB
74Accepted593ms5684 KiB
75Accepted657ms6196 KiB
subtask70/54
76Accepted1ms508 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms512 KiB
84Accepted1ms508 KiB
85Accepted3ms512 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted3ms528 KiB
89Accepted1ms316 KiB
90Wrong answer1ms508 KiB
91Accepted4ms508 KiB
92Accepted4ms316 KiB
93Accepted4ms316 KiB
94Accepted4ms316 KiB
95Accepted3ms356 KiB
96Accepted3ms316 KiB
97Wrong answer4ms536 KiB
98Accepted25ms940 KiB
99Accepted25ms820 KiB
100Accepted25ms944 KiB
101Accepted25ms820 KiB
102Accepted26ms1148 KiB
103Accepted25ms1072 KiB
104Accepted37ms820 KiB
105Accepted37ms1052 KiB
106Wrong answer37ms820 KiB
107Wrong answer37ms820 KiB
108Accepted27ms944 KiB
109Accepted28ms820 KiB
110Wrong answer28ms820 KiB
111Wrong answer39ms960 KiB
112Accepted1ms500 KiB
113Accepted2ms316 KiB
114Accepted582ms6192 KiB
115Accepted582ms6196 KiB
116Accepted630ms5940 KiB
117Accepted592ms5564 KiB
118Accepted654ms6196 KiB
119Wrong answer2ms508 KiB
120Accepted2ms508 KiB
121Accepted583ms6200 KiB
122Accepted584ms6268 KiB
123Accepted633ms5964 KiB
124Accepted593ms5684 KiB
125Accepted657ms6196 KiB
126Accepted1ms316 KiB
127Wrong answer2ms316 KiB
128Wrong answer791ms6272 KiB
129Accepted786ms6276 KiB
130Wrong answer824ms6108 KiB
131Wrong answer774ms5684 KiB
132Accepted657ms6196 KiB
133Accepted662ms6196 KiB
134Wrong answer675ms6056 KiB
135Accepted686ms6196 KiB
136Accepted857ms6196 KiB