250102026-02-17 12:28:45Leventusz09Maximális összegű útcpp17Wrong answer 4/100493ms6268 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];
                    }
                }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
2Accepted1ms504 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms544 KiB
5Accepted1ms316 KiB
6Accepted2ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms544 KiB
10Accepted1ms316 KiB
11Accepted2ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms508 KiB
15Wrong answer2ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms316 KiB
18Wrong answer3ms320 KiB
19Wrong answer1ms560 KiB
20Wrong answer2ms316 KiB
21Wrong answer2ms316 KiB
22Wrong answer2ms396 KiB
23Wrong answer3ms316 KiB
24Accepted3ms316 KiB
25Wrong answer3ms316 KiB
26Wrong answer3ms328 KiB
27Wrong answer3ms532 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms544 KiB
30Accepted1ms316 KiB
31Accepted2ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms508 KiB
35Wrong answer2ms316 KiB
36Accepted1ms508 KiB
37Accepted1ms316 KiB
38Wrong answer3ms320 KiB
39Wrong answer1ms560 KiB
40Wrong answer2ms316 KiB
41Wrong answer2ms316 KiB
42Wrong answer2ms396 KiB
43Wrong answer3ms316 KiB
44Accepted3ms316 KiB
45Wrong answer3ms316 KiB
46Wrong answer3ms328 KiB
47Wrong answer3ms532 KiB
48Wrong answer17ms820 KiB
49Wrong answer17ms820 KiB
50Wrong answer17ms944 KiB
51Wrong answer17ms944 KiB
52Wrong answer17ms820 KiB
53Wrong answer17ms824 KiB
54Wrong answer18ms948 KiB
55Wrong answer18ms820 KiB
56Wrong answer19ms940 KiB
57Wrong answer19ms708 KiB
58Wrong answer19ms812 KiB
59Wrong answer19ms952 KiB
60Wrong answer20ms944 KiB
61Wrong answer20ms960 KiB
subtask50/5
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted402ms6220 KiB
65Wrong answer405ms6028 KiB
66Accepted458ms5952 KiB
67Accepted430ms5676 KiB
68Accepted477ms6196 KiB
subtask60/12
69Accepted1ms508 KiB
70Accepted1ms316 KiB
71Wrong answer407ms6196 KiB
72Wrong answer404ms6196 KiB
73Wrong answer460ms6036 KiB
74Accepted430ms5512 KiB
75Accepted476ms6188 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms500 KiB
78Accepted1ms316 KiB
79Accepted1ms544 KiB
80Accepted1ms316 KiB
81Accepted2ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms508 KiB
85Wrong answer2ms316 KiB
86Accepted1ms508 KiB
87Accepted1ms316 KiB
88Wrong answer3ms320 KiB
89Wrong answer1ms560 KiB
90Wrong answer2ms316 KiB
91Wrong answer2ms316 KiB
92Wrong answer2ms396 KiB
93Wrong answer3ms316 KiB
94Accepted3ms316 KiB
95Wrong answer3ms316 KiB
96Wrong answer3ms328 KiB
97Wrong answer3ms532 KiB
98Wrong answer17ms820 KiB
99Wrong answer17ms820 KiB
100Wrong answer17ms944 KiB
101Wrong answer17ms944 KiB
102Wrong answer17ms820 KiB
103Wrong answer17ms824 KiB
104Wrong answer18ms948 KiB
105Wrong answer18ms820 KiB
106Wrong answer19ms940 KiB
107Wrong answer19ms708 KiB
108Wrong answer19ms812 KiB
109Wrong answer19ms952 KiB
110Wrong answer20ms944 KiB
111Wrong answer20ms960 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted402ms6220 KiB
115Wrong answer405ms6028 KiB
116Accepted458ms5952 KiB
117Accepted430ms5676 KiB
118Accepted477ms6196 KiB
119Accepted1ms508 KiB
120Accepted1ms316 KiB
121Wrong answer407ms6196 KiB
122Wrong answer404ms6196 KiB
123Wrong answer460ms6036 KiB
124Accepted430ms5512 KiB
125Accepted476ms6188 KiB
126Wrong answer1ms316 KiB
127Wrong answer1ms316 KiB
128Wrong answer421ms6136 KiB
129Wrong answer421ms6048 KiB
130Wrong answer477ms6088 KiB
131Wrong answer449ms5624 KiB
132Accepted477ms6268 KiB
133Wrong answer479ms6268 KiB
134Wrong answer486ms6196 KiB
135Wrong answer486ms6260 KiB
136Wrong answer493ms6204 KiB