249912026-02-17 11:30:11Leventusz09Maximális összegű útcpp17Hibás válasz 0/100469ms262144 KiB
#include <iostream>
#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=0;

    // bal felső sarok
    IC L[0][0][c] = 0;
    L[0][0][C[0][0]] = A[0][0];
    if(A[0][0] > o) o = A[0][0];

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

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

            if(C[i][0] == c) if(L[i][0][c] > o) o = L[i][0][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
1Elfogadva1ms512 KiB
2Elfogadva1ms316 KiB
subtask20/4
3Hibás válasz1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Hibás válasz1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva2ms564 KiB
15Elfogadva6ms3892 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms592 KiB
18Elfogadva4ms3892 KiB
19Hibás válasz1ms540 KiB
20Hibás válasz1ms564 KiB
21Hibás válasz6ms3836 KiB
22Hibás válasz4ms3200 KiB
23Hibás válasz6ms3380 KiB
24Hibás válasz4ms3892 KiB
25Elfogadva6ms3892 KiB
26Hibás válasz6ms3892 KiB
27Hibás válasz4ms3892 KiB
subtask40/18
28Hibás válasz1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva2ms564 KiB
35Elfogadva6ms3892 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms592 KiB
38Elfogadva4ms3892 KiB
39Hibás válasz1ms540 KiB
40Hibás válasz1ms564 KiB
41Hibás válasz6ms3836 KiB
42Hibás válasz4ms3200 KiB
43Hibás válasz6ms3380 KiB
44Hibás válasz4ms3892 KiB
45Elfogadva6ms3892 KiB
46Hibás válasz6ms3892 KiB
47Hibás válasz4ms3892 KiB
48Hibás válasz43ms39668 KiB
49Elfogadva50ms39476 KiB
50Elfogadva43ms39476 KiB
51Elfogadva50ms39468 KiB
52Hibás válasz43ms39476 KiB
53Hibás válasz43ms39480 KiB
54Hibás válasz50ms39468 KiB
55Hibás válasz50ms39548 KiB
56Hibás válasz43ms36836 KiB
57Hibás válasz43ms37324 KiB
58Hibás válasz52ms39476 KiB
59Hibás válasz52ms39476 KiB
60Hibás válasz52ms39676 KiB
61Hibás válasz46ms39476 KiB
subtask50/5
62Elfogadva1ms316 KiB
63Elfogadva2ms764 KiB
64Futási hiba351ms262144 KiB
65Futási hiba347ms262144 KiB
66Futási hiba456ms262144 KiB
67Futási hiba449ms262144 KiB
68Futási hiba419ms262144 KiB
subtask60/12
69Elfogadva1ms540 KiB
70Elfogadva2ms756 KiB
71Futási hiba351ms262144 KiB
72Futási hiba395ms262144 KiB
73Futási hiba462ms262144 KiB
74Futási hiba402ms262144 KiB
75Futási hiba421ms262144 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms512 KiB
78Hibás válasz1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva2ms564 KiB
85Elfogadva6ms3892 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms592 KiB
88Elfogadva4ms3892 KiB
89Hibás válasz1ms540 KiB
90Hibás válasz1ms564 KiB
91Hibás válasz6ms3836 KiB
92Hibás válasz4ms3200 KiB
93Hibás válasz6ms3380 KiB
94Hibás válasz4ms3892 KiB
95Elfogadva6ms3892 KiB
96Hibás válasz6ms3892 KiB
97Hibás válasz4ms3892 KiB
98Hibás válasz43ms39668 KiB
99Elfogadva50ms39476 KiB
100Elfogadva43ms39476 KiB
101Elfogadva50ms39468 KiB
102Hibás válasz43ms39476 KiB
103Hibás válasz43ms39480 KiB
104Hibás válasz50ms39468 KiB
105Hibás válasz50ms39548 KiB
106Hibás válasz43ms36836 KiB
107Hibás válasz43ms37324 KiB
108Hibás válasz52ms39476 KiB
109Hibás válasz52ms39476 KiB
110Hibás válasz52ms39676 KiB
111Hibás válasz46ms39476 KiB
112Elfogadva1ms316 KiB
113Elfogadva2ms764 KiB
114Futási hiba351ms262144 KiB
115Futási hiba347ms262144 KiB
116Futási hiba456ms262144 KiB
117Futási hiba449ms262144 KiB
118Futási hiba419ms262144 KiB
119Elfogadva1ms540 KiB
120Elfogadva2ms756 KiB
121Futási hiba351ms262144 KiB
122Futási hiba395ms262144 KiB
123Futási hiba462ms262144 KiB
124Futási hiba402ms262144 KiB
125Futási hiba421ms262144 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz2ms564 KiB
128Futási hiba414ms262144 KiB
129Futási hiba368ms262144 KiB
130Futási hiba423ms262144 KiB
131Futási hiba465ms262144 KiB
132Futási hiba462ms262144 KiB
133Futási hiba414ms262144 KiB
134Futási hiba469ms262144 KiB
135Futási hiba423ms262144 KiB
136Futási hiba425ms262144 KiB