250142026-02-17 12:40:52Leventusz09Maximális összegű útcpp17Wrong answer 9/100834ms6244 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] = A[i][j];
                    }

                    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] = A[i][j];
                    }

                    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] = max(lu, ll) + A[i][j];
                }

                if(C[i][j] == c) if(LN[c] > o) o = LN[c];
            }
        }
    }
    
    
    
    /*// bal felső sarok
    int LL[M][500];
    int LN[500];
    int o=A[0][0];


    IC LC[0][c] = 0;
    IC LL[0][c] = 0;
    LN[C[0][0]] = A[0][0];

    // első sor
    for(int i=1; i<M; i++){
        IC{
            if(LN[c] > 0 || C[0][i] == c){
                LN[c] += A[0][i];
            }else{
                LN[c] = 0;
            }

            if(C[0][i] == c) if(LN[c] > o) o = LN[c];

            LL[i][c] = LN[c];
        }
    }
    
    //első oszlop
    IC LN[c] = 0;
    LN[C[0][0]] = A[0][0];
    for(int i=1; i<N; i++){
        IC{
            if(LN[c] > 0 || C[i][0] == c){
                LN[c] += A[i][0];
            }else{
                LN[c] = 0;
            }

            if(C[i][0] == c) if(LN[c] > o) o = LN[c];

            LC[i][c] = LN[c];
        }
    }

    // az összes többi
    for(int i=1; i<N; i++){
        for(int j=1; j<M; j++){
            IC{
                int cu = L[i-1][j][c];
                int cl = L[i][j-1][c];
                if(cu < 0 && cl < 0){
                    if(C[i][j] == c) L[i][j][c] = A[i][j];
                    else L[i][j][c] = max(cu, cl) + A[i][j];
                }
                else L[i][j][c] = max(cu, cl) + A[i][j];

                if(C[i][j] == c) if(L[i][j][c] > o) o = L[i][j][c];
            }
        }
    }*/
    #if DEBUG
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            IC{
                cout << L[i][j][c] << ".";
            }
            cout << "\t";
        }
        cout << "\n";
    }

    #endif
    cout << o << endl;
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms500 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms388 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms388 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms508 KiB
14Accepted2ms316 KiB
15Accepted4ms500 KiB
16Accepted1ms316 KiB
17Accepted2ms440 KiB
18Accepted4ms316 KiB
19Wrong answer2ms500 KiB
20Wrong answer2ms332 KiB
21Wrong answer4ms500 KiB
22Wrong answer4ms536 KiB
23Wrong answer4ms316 KiB
24Accepted4ms408 KiB
25Wrong answer4ms316 KiB
26Wrong answer4ms316 KiB
27Wrong answer4ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms388 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms508 KiB
34Accepted2ms316 KiB
35Accepted4ms500 KiB
36Accepted1ms316 KiB
37Accepted2ms440 KiB
38Accepted4ms316 KiB
39Wrong answer2ms500 KiB
40Wrong answer2ms332 KiB
41Wrong answer4ms500 KiB
42Wrong answer4ms536 KiB
43Wrong answer4ms316 KiB
44Accepted4ms408 KiB
45Wrong answer4ms316 KiB
46Wrong answer4ms316 KiB
47Wrong answer4ms316 KiB
48Accepted30ms820 KiB
49Accepted30ms1012 KiB
50Accepted30ms940 KiB
51Accepted30ms820 KiB
52Accepted30ms820 KiB
53Wrong answer30ms944 KiB
54Wrong answer32ms1016 KiB
55Wrong answer32ms948 KiB
56Wrong answer32ms820 KiB
57Wrong answer32ms820 KiB
58Accepted34ms820 KiB
59Wrong answer34ms1016 KiB
60Wrong answer34ms1012 KiB
61Wrong answer35ms948 KiB
subtask55/5
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted754ms6196 KiB
65Accepted754ms6200 KiB
66Accepted787ms5876 KiB
67Accepted740ms5520 KiB
68Accepted819ms6196 KiB
subtask60/12
69Accepted2ms316 KiB
70Accepted2ms316 KiB
71Wrong answer755ms6196 KiB
72Accepted757ms6072 KiB
73Wrong answer787ms5940 KiB
74Accepted741ms5680 KiB
75Accepted819ms6200 KiB
subtask70/54
76Accepted1ms800 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms388 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms508 KiB
84Accepted2ms316 KiB
85Accepted4ms500 KiB
86Accepted1ms316 KiB
87Accepted2ms440 KiB
88Accepted4ms316 KiB
89Wrong answer2ms500 KiB
90Wrong answer2ms332 KiB
91Wrong answer4ms500 KiB
92Wrong answer4ms536 KiB
93Wrong answer4ms316 KiB
94Accepted4ms408 KiB
95Wrong answer4ms316 KiB
96Wrong answer4ms316 KiB
97Wrong answer4ms316 KiB
98Accepted30ms820 KiB
99Accepted30ms1012 KiB
100Accepted30ms940 KiB
101Accepted30ms820 KiB
102Accepted30ms820 KiB
103Wrong answer30ms944 KiB
104Wrong answer32ms1016 KiB
105Wrong answer32ms948 KiB
106Wrong answer32ms820 KiB
107Wrong answer32ms820 KiB
108Accepted34ms820 KiB
109Wrong answer34ms1016 KiB
110Wrong answer34ms1012 KiB
111Wrong answer35ms948 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted754ms6196 KiB
115Accepted754ms6200 KiB
116Accepted787ms5876 KiB
117Accepted740ms5520 KiB
118Accepted819ms6196 KiB
119Accepted2ms316 KiB
120Accepted2ms316 KiB
121Wrong answer755ms6196 KiB
122Accepted757ms6072 KiB
123Wrong answer787ms5940 KiB
124Accepted741ms5680 KiB
125Accepted819ms6200 KiB
126Wrong answer1ms316 KiB
127Wrong answer2ms440 KiB
128Wrong answer771ms6200 KiB
129Wrong answer771ms6064 KiB
130Wrong answer805ms5956 KiB
131Wrong answer754ms5532 KiB
132Accepted820ms6196 KiB
133Wrong answer820ms6096 KiB
134Wrong answer827ms6244 KiB
135Wrong answer829ms6116 KiB
136Wrong answer834ms6244 KiB