249902026-02-17 11:29:00Leventusz09Maximális összegű útcpp17Hibás válasz 0/100587ms262144 KiB
#include <iostream>
#define DEBUG false

#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
1Elfogadva1ms508 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
14Elfogadva1ms564 KiB
15Elfogadva4ms2100 KiB
16Elfogadva1ms508 KiB
17Elfogadva1ms564 KiB
18Elfogadva4ms2100 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms564 KiB
21Hibás válasz4ms2100 KiB
22Hibás válasz3ms1676 KiB
23Hibás válasz4ms1844 KiB
24Hibás válasz3ms2012 KiB
25Hibás válasz4ms2004 KiB
26Hibás válasz4ms2100 KiB
27Hibás válasz4ms2100 KiB
subtask40/18
28Hibás válasz1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms564 KiB
35Elfogadva4ms2100 KiB
36Elfogadva1ms508 KiB
37Elfogadva1ms564 KiB
38Elfogadva4ms2100 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms564 KiB
41Hibás válasz4ms2100 KiB
42Hibás válasz3ms1676 KiB
43Hibás válasz4ms1844 KiB
44Hibás válasz3ms2012 KiB
45Hibás válasz4ms2004 KiB
46Hibás válasz4ms2100 KiB
47Hibás válasz4ms2100 KiB
48Hibás válasz30ms19880 KiB
49Elfogadva28ms19988 KiB
50Elfogadva28ms19936 KiB
51Elfogadva30ms19936 KiB
52Hibás válasz28ms20020 KiB
53Hibás válasz28ms19820 KiB
54Hibás válasz32ms20020 KiB
55Hibás válasz28ms20032 KiB
56Hibás válasz29ms18500 KiB
57Hibás válasz30ms18740 KiB
58Hibás válasz34ms20016 KiB
59Hibás válasz34ms20020 KiB
60Hibás válasz35ms19932 KiB
61Hibás válasz32ms20024 KiB
subtask50/5
62Elfogadva2ms500 KiB
63Elfogadva2ms564 KiB
64Futási hiba404ms262144 KiB
65Futási hiba451ms262144 KiB
66Futási hiba524ms262144 KiB
67Futási hiba469ms262144 KiB
68Futási hiba486ms262144 KiB
subtask60/12
69Elfogadva2ms316 KiB
70Elfogadva2ms564 KiB
71Futási hiba402ms262144 KiB
72Futási hiba407ms262144 KiB
73Futási hiba522ms262144 KiB
74Futási hiba512ms262144 KiB
75Futási hiba483ms262144 KiB
subtask70/54
76Elfogadva1ms500 KiB
77Elfogadva1ms508 KiB
78Hibás válasz1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms564 KiB
85Elfogadva4ms2100 KiB
86Elfogadva1ms508 KiB
87Elfogadva1ms564 KiB
88Elfogadva4ms2100 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms564 KiB
91Hibás válasz4ms2100 KiB
92Hibás válasz3ms1676 KiB
93Hibás válasz4ms1844 KiB
94Hibás válasz3ms2012 KiB
95Hibás válasz4ms2004 KiB
96Hibás válasz4ms2100 KiB
97Hibás válasz4ms2100 KiB
98Hibás válasz30ms19880 KiB
99Elfogadva28ms19988 KiB
100Elfogadva28ms19936 KiB
101Elfogadva30ms19936 KiB
102Hibás válasz28ms20020 KiB
103Hibás válasz28ms19820 KiB
104Hibás válasz32ms20020 KiB
105Hibás válasz28ms20032 KiB
106Hibás válasz29ms18500 KiB
107Hibás válasz30ms18740 KiB
108Hibás válasz34ms20016 KiB
109Hibás válasz34ms20020 KiB
110Hibás válasz35ms19932 KiB
111Hibás válasz32ms20024 KiB
112Elfogadva2ms500 KiB
113Elfogadva2ms564 KiB
114Futási hiba404ms262144 KiB
115Futási hiba451ms262144 KiB
116Futási hiba524ms262144 KiB
117Futási hiba469ms262144 KiB
118Futási hiba486ms262144 KiB
119Elfogadva2ms316 KiB
120Elfogadva2ms564 KiB
121Futási hiba402ms262144 KiB
122Futási hiba407ms262144 KiB
123Futási hiba522ms262144 KiB
124Futási hiba512ms262144 KiB
125Futási hiba483ms262144 KiB
126Hibás válasz1ms508 KiB
127Hibás válasz1ms564 KiB
128Futási hiba421ms262144 KiB
129Futási hiba416ms262144 KiB
130Futási hiba587ms262144 KiB
131Futási hiba584ms262144 KiB
132Futási hiba476ms262144 KiB
133Futási hiba485ms262144 KiB
134Futási hiba537ms262144 KiB
135Futási hiba545ms262144 KiB
136Futási hiba550ms262144 KiB