251802026-02-18 11:39:04Leventusz09Maximális összegű útcpp17Wrong answer 21/100486ms6204 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{
                        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
2Accepted1ms316 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted2ms504 KiB
6Accepted1ms508 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted2ms504 KiB
11Accepted1ms508 KiB
12Accepted1ms316 KiB
13Accepted1ms332 KiB
14Accepted1ms500 KiB
15Accepted3ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted2ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer3ms508 KiB
22Wrong answer3ms316 KiB
23Wrong answer3ms316 KiB
24Accepted3ms552 KiB
25Accepted3ms408 KiB
26Wrong answer3ms316 KiB
27Wrong answer3ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted2ms504 KiB
31Accepted1ms508 KiB
32Accepted1ms316 KiB
33Accepted1ms332 KiB
34Accepted1ms500 KiB
35Accepted3ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted2ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer3ms508 KiB
42Wrong answer3ms316 KiB
43Wrong answer3ms316 KiB
44Accepted3ms552 KiB
45Accepted3ms408 KiB
46Wrong answer3ms316 KiB
47Wrong answer3ms316 KiB
48Accepted17ms820 KiB
49Accepted17ms944 KiB
50Accepted17ms952 KiB
51Accepted17ms944 KiB
52Accepted17ms944 KiB
53Accepted17ms948 KiB
54Wrong answer17ms812 KiB
55Wrong answer17ms944 KiB
56Wrong answer20ms820 KiB
57Wrong answer19ms820 KiB
58Accepted20ms820 KiB
59Accepted20ms828 KiB
60Wrong answer19ms820 KiB
61Wrong answer20ms948 KiB
subtask55/5
62Accepted1ms508 KiB
63Accepted1ms316 KiB
64Accepted400ms6196 KiB
65Accepted398ms6056 KiB
66Accepted449ms5868 KiB
67Accepted423ms5708 KiB
68Accepted469ms6192 KiB
subtask612/12
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Accepted400ms6196 KiB
72Accepted402ms6192 KiB
73Accepted451ms5940 KiB
74Accepted423ms5684 KiB
75Accepted469ms6052 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted2ms504 KiB
81Accepted1ms508 KiB
82Accepted1ms316 KiB
83Accepted1ms332 KiB
84Accepted1ms500 KiB
85Accepted3ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted2ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer3ms508 KiB
92Wrong answer3ms316 KiB
93Wrong answer3ms316 KiB
94Accepted3ms552 KiB
95Accepted3ms408 KiB
96Wrong answer3ms316 KiB
97Wrong answer3ms316 KiB
98Accepted17ms820 KiB
99Accepted17ms944 KiB
100Accepted17ms952 KiB
101Accepted17ms944 KiB
102Accepted17ms944 KiB
103Accepted17ms948 KiB
104Wrong answer17ms812 KiB
105Wrong answer17ms944 KiB
106Wrong answer20ms820 KiB
107Wrong answer19ms820 KiB
108Accepted20ms820 KiB
109Accepted20ms828 KiB
110Wrong answer19ms820 KiB
111Wrong answer20ms948 KiB
112Accepted1ms508 KiB
113Accepted1ms316 KiB
114Accepted400ms6196 KiB
115Accepted398ms6056 KiB
116Accepted449ms5868 KiB
117Accepted423ms5708 KiB
118Accepted469ms6192 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted400ms6196 KiB
122Accepted402ms6192 KiB
123Accepted451ms5940 KiB
124Accepted423ms5684 KiB
125Accepted469ms6052 KiB
126Wrong answer1ms316 KiB
127Wrong answer1ms316 KiB
128Wrong answer416ms6104 KiB
129Wrong answer419ms6164 KiB
130Wrong answer465ms5940 KiB
131Wrong answer441ms5468 KiB
132Accepted470ms6196 KiB
133Accepted470ms6192 KiB
134Wrong answer477ms6180 KiB
135Wrong answer476ms6092 KiB
136Wrong answer486ms6204 KiB