250102026-02-17 12:28:45Leventusz09Maximális összegű útcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms504 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms544 KiB
5Elfogadva1ms316 KiB
6Elfogadva2ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms544 KiB
10Elfogadva1ms316 KiB
11Elfogadva2ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms508 KiB
15Hibás válasz2ms316 KiB
16Elfogadva1ms508 KiB
17Elfogadva1ms316 KiB
18Hibás válasz3ms320 KiB
19Hibás válasz1ms560 KiB
20Hibás válasz2ms316 KiB
21Hibás válasz2ms316 KiB
22Hibás válasz2ms396 KiB
23Hibás válasz3ms316 KiB
24Elfogadva3ms316 KiB
25Hibás válasz3ms316 KiB
26Hibás válasz3ms328 KiB
27Hibás válasz3ms532 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms544 KiB
30Elfogadva1ms316 KiB
31Elfogadva2ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms508 KiB
35Hibás válasz2ms316 KiB
36Elfogadva1ms508 KiB
37Elfogadva1ms316 KiB
38Hibás válasz3ms320 KiB
39Hibás válasz1ms560 KiB
40Hibás válasz2ms316 KiB
41Hibás válasz2ms316 KiB
42Hibás válasz2ms396 KiB
43Hibás válasz3ms316 KiB
44Elfogadva3ms316 KiB
45Hibás válasz3ms316 KiB
46Hibás válasz3ms328 KiB
47Hibás válasz3ms532 KiB
48Hibás válasz17ms820 KiB
49Hibás válasz17ms820 KiB
50Hibás válasz17ms944 KiB
51Hibás válasz17ms944 KiB
52Hibás válasz17ms820 KiB
53Hibás válasz17ms824 KiB
54Hibás válasz18ms948 KiB
55Hibás válasz18ms820 KiB
56Hibás válasz19ms940 KiB
57Hibás válasz19ms708 KiB
58Hibás válasz19ms812 KiB
59Hibás válasz19ms952 KiB
60Hibás válasz20ms944 KiB
61Hibás válasz20ms960 KiB
subtask50/5
62Elfogadva1ms316 KiB
63Elfogadva1ms316 KiB
64Elfogadva402ms6220 KiB
65Hibás válasz405ms6028 KiB
66Elfogadva458ms5952 KiB
67Elfogadva430ms5676 KiB
68Elfogadva477ms6196 KiB
subtask60/12
69Elfogadva1ms508 KiB
70Elfogadva1ms316 KiB
71Hibás válasz407ms6196 KiB
72Hibás válasz404ms6196 KiB
73Hibás válasz460ms6036 KiB
74Elfogadva430ms5512 KiB
75Elfogadva476ms6188 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms500 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms544 KiB
80Elfogadva1ms316 KiB
81Elfogadva2ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms508 KiB
85Hibás válasz2ms316 KiB
86Elfogadva1ms508 KiB
87Elfogadva1ms316 KiB
88Hibás válasz3ms320 KiB
89Hibás válasz1ms560 KiB
90Hibás válasz2ms316 KiB
91Hibás válasz2ms316 KiB
92Hibás válasz2ms396 KiB
93Hibás válasz3ms316 KiB
94Elfogadva3ms316 KiB
95Hibás válasz3ms316 KiB
96Hibás válasz3ms328 KiB
97Hibás válasz3ms532 KiB
98Hibás válasz17ms820 KiB
99Hibás válasz17ms820 KiB
100Hibás válasz17ms944 KiB
101Hibás válasz17ms944 KiB
102Hibás válasz17ms820 KiB
103Hibás válasz17ms824 KiB
104Hibás válasz18ms948 KiB
105Hibás válasz18ms820 KiB
106Hibás válasz19ms940 KiB
107Hibás válasz19ms708 KiB
108Hibás válasz19ms812 KiB
109Hibás válasz19ms952 KiB
110Hibás válasz20ms944 KiB
111Hibás válasz20ms960 KiB
112Elfogadva1ms316 KiB
113Elfogadva1ms316 KiB
114Elfogadva402ms6220 KiB
115Hibás válasz405ms6028 KiB
116Elfogadva458ms5952 KiB
117Elfogadva430ms5676 KiB
118Elfogadva477ms6196 KiB
119Elfogadva1ms508 KiB
120Elfogadva1ms316 KiB
121Hibás válasz407ms6196 KiB
122Hibás válasz404ms6196 KiB
123Hibás válasz460ms6036 KiB
124Elfogadva430ms5512 KiB
125Elfogadva476ms6188 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz421ms6136 KiB
129Hibás válasz421ms6048 KiB
130Hibás válasz477ms6088 KiB
131Hibás válasz449ms5624 KiB
132Elfogadva477ms6268 KiB
133Hibás válasz479ms6268 KiB
134Hibás válasz486ms6196 KiB
135Hibás válasz486ms6260 KiB
136Hibás válasz493ms6204 KiB