251562026-02-18 09:44:31Leventusz09Maximális összegű útcpp17Hibás válasz 4/100667ms6268 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){
                    // bal felső sarok
                    LN[c] = 0;
                    if(C[0][0] == c) LN[c] = A[0][0];
                    LR[0][c] = LN[c];
                }else
                if(i == 0){
                    // első sor
                    if(LN[c] > 0){
                        LN[c] += A[i][j];
                    }else{
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }
                    
                    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] = C[i][j] == c ? A[i][j] : 0;
                    }

                    LR[j][c] = LN[c];
                }else{
                    int lu = LR[j][c];
                    int ll = LN[c];
                    if(lu < 0 && ll < 0){
                        if(C[i][j] == c){
                            LN[c] = A[i][j];
                        }else{
                            LN[c] = max(lu, ll) + A[i][j];
                        }
                    //}else LN[c] = C[i][j] == c ? max(lu, ll) + A[i][j] : 0;
                    }else if(lu == 0 || ll == 0){
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }else LN[c] = max(lu, ll) + A[i][j];

                    LR[j][c] = LN[c];
                }
                if(C[i][j] == c) if(LN[c] > o) o = LN[c];
            }
        }

        #if DEBUG
        for(int i=0; i<M; i++){
            IC{
                cout << LR[i][c] << ".";
            }
            cout << " ";
        }
        cout << endl;
        #endif
    }

    cout << o << endl;
    
    return 0;
}

/*
3 3
1 1 1
1 1 1
1 1 1
1 2 3
4 5 6
7 8 9

*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Elfogadva1ms316 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Hibás válasz1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva3ms316 KiB
16Hibás válasz1ms376 KiB
17Elfogadva1ms316 KiB
18Hibás válasz3ms316 KiB
19Elfogadva1ms316 KiB
20Hibás válasz1ms416 KiB
21Hibás válasz3ms316 KiB
22Hibás válasz3ms316 KiB
23Hibás válasz3ms316 KiB
24Elfogadva3ms412 KiB
25Hibás válasz3ms316 KiB
26Hibás válasz3ms316 KiB
27Hibás válasz3ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Hibás válasz1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva3ms316 KiB
36Hibás válasz1ms376 KiB
37Elfogadva1ms316 KiB
38Hibás válasz3ms316 KiB
39Elfogadva1ms316 KiB
40Hibás válasz1ms416 KiB
41Hibás válasz3ms316 KiB
42Hibás válasz3ms316 KiB
43Hibás válasz3ms316 KiB
44Elfogadva3ms412 KiB
45Hibás válasz3ms316 KiB
46Hibás válasz3ms316 KiB
47Hibás válasz3ms316 KiB
48Hibás válasz25ms936 KiB
49Elfogadva24ms944 KiB
50Hibás válasz25ms712 KiB
51Hibás válasz25ms948 KiB
52Hibás válasz25ms1072 KiB
53Hibás válasz25ms788 KiB
54Hibás válasz26ms1012 KiB
55Hibás válasz26ms820 KiB
56Hibás válasz27ms840 KiB
57Hibás válasz27ms1012 KiB
58Elfogadva28ms1056 KiB
59Elfogadva28ms1012 KiB
60Hibás válasz28ms1008 KiB
61Hibás válasz28ms768 KiB
subtask50/5
62Hibás válasz1ms316 KiB
63Elfogadva1ms500 KiB
64Elfogadva578ms6208 KiB
65Elfogadva579ms6196 KiB
66Elfogadva620ms5892 KiB
67Elfogadva583ms5544 KiB
68Elfogadva647ms6196 KiB
subtask60/12
69Hibás válasz1ms316 KiB
70Elfogadva1ms316 KiB
71Hibás válasz582ms6192 KiB
72Hibás válasz580ms6268 KiB
73Hibás válasz625ms5940 KiB
74Elfogadva586ms5680 KiB
75Hibás válasz648ms6192 KiB
subtask70/54
76Elfogadva1ms508 KiB
77Elfogadva1ms508 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Hibás válasz1ms316 KiB
84Elfogadva1ms316 KiB
85Elfogadva3ms316 KiB
86Hibás válasz1ms376 KiB
87Elfogadva1ms316 KiB
88Hibás válasz3ms316 KiB
89Elfogadva1ms316 KiB
90Hibás válasz1ms416 KiB
91Hibás válasz3ms316 KiB
92Hibás válasz3ms316 KiB
93Hibás válasz3ms316 KiB
94Elfogadva3ms412 KiB
95Hibás válasz3ms316 KiB
96Hibás válasz3ms316 KiB
97Hibás válasz3ms316 KiB
98Hibás válasz25ms936 KiB
99Elfogadva24ms944 KiB
100Hibás válasz25ms712 KiB
101Hibás válasz25ms948 KiB
102Hibás válasz25ms1072 KiB
103Hibás válasz25ms788 KiB
104Hibás válasz26ms1012 KiB
105Hibás válasz26ms820 KiB
106Hibás válasz27ms840 KiB
107Hibás válasz27ms1012 KiB
108Elfogadva28ms1056 KiB
109Elfogadva28ms1012 KiB
110Hibás válasz28ms1008 KiB
111Hibás válasz28ms768 KiB
112Hibás válasz1ms316 KiB
113Elfogadva1ms500 KiB
114Elfogadva578ms6208 KiB
115Elfogadva579ms6196 KiB
116Elfogadva620ms5892 KiB
117Elfogadva583ms5544 KiB
118Elfogadva647ms6196 KiB
119Hibás válasz1ms316 KiB
120Elfogadva1ms316 KiB
121Hibás válasz582ms6192 KiB
122Hibás válasz580ms6268 KiB
123Hibás válasz625ms5940 KiB
124Elfogadva586ms5680 KiB
125Hibás válasz648ms6192 KiB
126Elfogadva1ms316 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz600ms6208 KiB
129Hibás válasz601ms6056 KiB
130Hibás válasz642ms6120 KiB
131Hibás válasz603ms5672 KiB
132Hibás válasz648ms6196 KiB
133Hibás válasz656ms6028 KiB
134Hibás válasz662ms6196 KiB
135Hibás válasz661ms6196 KiB
136Hibás válasz667ms6196 KiB