251562026-02-18 09:44:31Leventusz09Maximális összegű útcpp17Wrong answer 4/100667ms6268 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(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
        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
1Accepted1ms508 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
13Wrong answer1ms316 KiB
14Accepted1ms316 KiB
15Accepted3ms316 KiB
16Wrong answer1ms376 KiB
17Accepted1ms316 KiB
18Wrong answer3ms316 KiB
19Accepted1ms316 KiB
20Wrong answer1ms416 KiB
21Wrong answer3ms316 KiB
22Wrong answer3ms316 KiB
23Wrong answer3ms316 KiB
24Accepted3ms412 KiB
25Wrong answer3ms316 KiB
26Wrong answer3ms316 KiB
27Wrong answer3ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Wrong answer1ms316 KiB
34Accepted1ms316 KiB
35Accepted3ms316 KiB
36Wrong answer1ms376 KiB
37Accepted1ms316 KiB
38Wrong answer3ms316 KiB
39Accepted1ms316 KiB
40Wrong answer1ms416 KiB
41Wrong answer3ms316 KiB
42Wrong answer3ms316 KiB
43Wrong answer3ms316 KiB
44Accepted3ms412 KiB
45Wrong answer3ms316 KiB
46Wrong answer3ms316 KiB
47Wrong answer3ms316 KiB
48Wrong answer25ms936 KiB
49Accepted24ms944 KiB
50Wrong answer25ms712 KiB
51Wrong answer25ms948 KiB
52Wrong answer25ms1072 KiB
53Wrong answer25ms788 KiB
54Wrong answer26ms1012 KiB
55Wrong answer26ms820 KiB
56Wrong answer27ms840 KiB
57Wrong answer27ms1012 KiB
58Accepted28ms1056 KiB
59Accepted28ms1012 KiB
60Wrong answer28ms1008 KiB
61Wrong answer28ms768 KiB
subtask50/5
62Wrong answer1ms316 KiB
63Accepted1ms500 KiB
64Accepted578ms6208 KiB
65Accepted579ms6196 KiB
66Accepted620ms5892 KiB
67Accepted583ms5544 KiB
68Accepted647ms6196 KiB
subtask60/12
69Wrong answer1ms316 KiB
70Accepted1ms316 KiB
71Wrong answer582ms6192 KiB
72Wrong answer580ms6268 KiB
73Wrong answer625ms5940 KiB
74Accepted586ms5680 KiB
75Wrong answer648ms6192 KiB
subtask70/54
76Accepted1ms508 KiB
77Accepted1ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Wrong answer1ms316 KiB
84Accepted1ms316 KiB
85Accepted3ms316 KiB
86Wrong answer1ms376 KiB
87Accepted1ms316 KiB
88Wrong answer3ms316 KiB
89Accepted1ms316 KiB
90Wrong answer1ms416 KiB
91Wrong answer3ms316 KiB
92Wrong answer3ms316 KiB
93Wrong answer3ms316 KiB
94Accepted3ms412 KiB
95Wrong answer3ms316 KiB
96Wrong answer3ms316 KiB
97Wrong answer3ms316 KiB
98Wrong answer25ms936 KiB
99Accepted24ms944 KiB
100Wrong answer25ms712 KiB
101Wrong answer25ms948 KiB
102Wrong answer25ms1072 KiB
103Wrong answer25ms788 KiB
104Wrong answer26ms1012 KiB
105Wrong answer26ms820 KiB
106Wrong answer27ms840 KiB
107Wrong answer27ms1012 KiB
108Accepted28ms1056 KiB
109Accepted28ms1012 KiB
110Wrong answer28ms1008 KiB
111Wrong answer28ms768 KiB
112Wrong answer1ms316 KiB
113Accepted1ms500 KiB
114Accepted578ms6208 KiB
115Accepted579ms6196 KiB
116Accepted620ms5892 KiB
117Accepted583ms5544 KiB
118Accepted647ms6196 KiB
119Wrong answer1ms316 KiB
120Accepted1ms316 KiB
121Wrong answer582ms6192 KiB
122Wrong answer580ms6268 KiB
123Wrong answer625ms5940 KiB
124Accepted586ms5680 KiB
125Wrong answer648ms6192 KiB
126Accepted1ms316 KiB
127Wrong answer2ms316 KiB
128Wrong answer600ms6208 KiB
129Wrong answer601ms6056 KiB
130Wrong answer642ms6120 KiB
131Wrong answer603ms5672 KiB
132Wrong answer648ms6196 KiB
133Wrong answer656ms6028 KiB
134Wrong answer662ms6196 KiB
135Wrong answer661ms6196 KiB
136Wrong answer667ms6196 KiB