250072026-02-17 12:14:38Leventusz09Maximális összegű útcpp17Wrong answer 4/100722ms9644 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 || c == C[i][j]){
                        LN[c] += A[i][j];
                    }else{
                        LN[c] = 0;
                    }

                    LR[j][c] = LN[c];
                }
                else if(j==0){
                    if(LR[0][c] > 0 || c == C[i][j]){
                        LN[c] = LR[0][c] + A[i][j];
                    }else{
                        LN[c] = 0;
                    }
                }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
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
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Wrong answer4ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms508 KiB
18Wrong answer3ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer3ms316 KiB
22Wrong answer3ms316 KiB
23Wrong answer3ms316 KiB
24Wrong answer4ms528 KiB
25Wrong answer3ms316 KiB
26Wrong answer4ms316 KiB
27Wrong answer4ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Wrong answer4ms316 KiB
36Accepted1ms508 KiB
37Accepted1ms508 KiB
38Wrong answer3ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer3ms316 KiB
42Wrong answer3ms316 KiB
43Wrong answer3ms316 KiB
44Wrong answer4ms528 KiB
45Wrong answer3ms316 KiB
46Wrong answer4ms316 KiB
47Wrong answer4ms316 KiB
48Wrong answer27ms1016 KiB
49Wrong answer27ms944 KiB
50Wrong answer27ms1064 KiB
51Wrong answer27ms820 KiB
52Wrong answer27ms908 KiB
53Wrong answer27ms1012 KiB
54Wrong answer28ms1012 KiB
55Wrong answer28ms820 KiB
56Wrong answer28ms820 KiB
57Wrong answer28ms820 KiB
58Wrong answer28ms1016 KiB
59Wrong answer28ms820 KiB
60Wrong answer28ms836 KiB
61Wrong answer29ms1080 KiB
subtask50/5
62Accepted2ms548 KiB
63Accepted2ms560 KiB
64Accepted638ms7224 KiB
65Wrong answer638ms7220 KiB
66Wrong answer675ms9032 KiB
67Accepted633ms7612 KiB
68Wrong answer703ms9268 KiB
subtask60/12
69Accepted2ms316 KiB
70Accepted2ms316 KiB
71Accepted638ms7368 KiB
72Wrong answer640ms7188 KiB
73Wrong answer683ms8876 KiB
74Accepted635ms8240 KiB
75Accepted703ms9268 KiB
subtask70/54
76Accepted2ms316 KiB
77Accepted2ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Wrong answer4ms316 KiB
86Accepted1ms508 KiB
87Accepted1ms508 KiB
88Wrong answer3ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer3ms316 KiB
92Wrong answer3ms316 KiB
93Wrong answer3ms316 KiB
94Wrong answer4ms528 KiB
95Wrong answer3ms316 KiB
96Wrong answer4ms316 KiB
97Wrong answer4ms316 KiB
98Wrong answer27ms1016 KiB
99Wrong answer27ms944 KiB
100Wrong answer27ms1064 KiB
101Wrong answer27ms820 KiB
102Wrong answer27ms908 KiB
103Wrong answer27ms1012 KiB
104Wrong answer28ms1012 KiB
105Wrong answer28ms820 KiB
106Wrong answer28ms820 KiB
107Wrong answer28ms820 KiB
108Wrong answer28ms1016 KiB
109Wrong answer28ms820 KiB
110Wrong answer28ms836 KiB
111Wrong answer29ms1080 KiB
112Accepted2ms548 KiB
113Accepted2ms560 KiB
114Accepted638ms7224 KiB
115Wrong answer638ms7220 KiB
116Wrong answer675ms9032 KiB
117Accepted633ms7612 KiB
118Wrong answer703ms9268 KiB
119Accepted2ms316 KiB
120Accepted2ms316 KiB
121Accepted638ms7368 KiB
122Wrong answer640ms7188 KiB
123Wrong answer683ms8876 KiB
124Accepted635ms8240 KiB
125Accepted703ms9268 KiB
126Wrong answer2ms316 KiB
127Wrong answer2ms316 KiB
128Wrong answer657ms7668 KiB
129Wrong answer653ms7648 KiB
130Wrong answer693ms9292 KiB
131Wrong answer652ms8592 KiB
132Accepted705ms9268 KiB
133Accepted707ms9076 KiB
134Wrong answer716ms8244 KiB
135Wrong answer712ms9468 KiB
136Wrong answer722ms9644 KiB