251392026-02-18 08:45:05Leventusz09Maximális összegű útcpp17Hibás válasz 9/100857ms6276 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] = 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
                    cout << "D" << i <<" " << j <<" "<<c<< endl;
                    #endif
                }
            }
        }

        #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
1Elfogadva1ms532 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
13Elfogadva1ms512 KiB
14Elfogadva1ms508 KiB
15Elfogadva3ms512 KiB
16Hibás válasz1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva3ms528 KiB
19Elfogadva1ms316 KiB
20Hibás válasz1ms508 KiB
21Elfogadva4ms508 KiB
22Elfogadva4ms316 KiB
23Elfogadva4ms316 KiB
24Elfogadva4ms316 KiB
25Elfogadva3ms356 KiB
26Elfogadva3ms316 KiB
27Hibás válasz4ms536 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms512 KiB
34Elfogadva1ms508 KiB
35Elfogadva3ms512 KiB
36Hibás válasz1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva3ms528 KiB
39Elfogadva1ms316 KiB
40Hibás válasz1ms508 KiB
41Elfogadva4ms508 KiB
42Elfogadva4ms316 KiB
43Elfogadva4ms316 KiB
44Elfogadva4ms316 KiB
45Elfogadva3ms356 KiB
46Elfogadva3ms316 KiB
47Hibás válasz4ms536 KiB
48Elfogadva25ms940 KiB
49Elfogadva25ms820 KiB
50Elfogadva25ms944 KiB
51Elfogadva25ms820 KiB
52Elfogadva26ms1148 KiB
53Elfogadva25ms1072 KiB
54Elfogadva37ms820 KiB
55Elfogadva37ms1052 KiB
56Hibás válasz37ms820 KiB
57Hibás válasz37ms820 KiB
58Elfogadva27ms944 KiB
59Elfogadva28ms820 KiB
60Hibás válasz28ms820 KiB
61Hibás válasz39ms960 KiB
subtask55/5
62Elfogadva1ms500 KiB
63Elfogadva2ms316 KiB
64Elfogadva582ms6192 KiB
65Elfogadva582ms6196 KiB
66Elfogadva630ms5940 KiB
67Elfogadva592ms5564 KiB
68Elfogadva654ms6196 KiB
subtask60/12
69Hibás válasz2ms508 KiB
70Elfogadva2ms508 KiB
71Elfogadva583ms6200 KiB
72Elfogadva584ms6268 KiB
73Elfogadva633ms5964 KiB
74Elfogadva593ms5684 KiB
75Elfogadva657ms6196 KiB
subtask70/54
76Elfogadva1ms508 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms512 KiB
84Elfogadva1ms508 KiB
85Elfogadva3ms512 KiB
86Hibás válasz1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva3ms528 KiB
89Elfogadva1ms316 KiB
90Hibás válasz1ms508 KiB
91Elfogadva4ms508 KiB
92Elfogadva4ms316 KiB
93Elfogadva4ms316 KiB
94Elfogadva4ms316 KiB
95Elfogadva3ms356 KiB
96Elfogadva3ms316 KiB
97Hibás válasz4ms536 KiB
98Elfogadva25ms940 KiB
99Elfogadva25ms820 KiB
100Elfogadva25ms944 KiB
101Elfogadva25ms820 KiB
102Elfogadva26ms1148 KiB
103Elfogadva25ms1072 KiB
104Elfogadva37ms820 KiB
105Elfogadva37ms1052 KiB
106Hibás válasz37ms820 KiB
107Hibás válasz37ms820 KiB
108Elfogadva27ms944 KiB
109Elfogadva28ms820 KiB
110Hibás válasz28ms820 KiB
111Hibás válasz39ms960 KiB
112Elfogadva1ms500 KiB
113Elfogadva2ms316 KiB
114Elfogadva582ms6192 KiB
115Elfogadva582ms6196 KiB
116Elfogadva630ms5940 KiB
117Elfogadva592ms5564 KiB
118Elfogadva654ms6196 KiB
119Hibás válasz2ms508 KiB
120Elfogadva2ms508 KiB
121Elfogadva583ms6200 KiB
122Elfogadva584ms6268 KiB
123Elfogadva633ms5964 KiB
124Elfogadva593ms5684 KiB
125Elfogadva657ms6196 KiB
126Elfogadva1ms316 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz791ms6272 KiB
129Elfogadva786ms6276 KiB
130Hibás válasz824ms6108 KiB
131Hibás válasz774ms5684 KiB
132Elfogadva657ms6196 KiB
133Elfogadva662ms6196 KiB
134Hibás válasz675ms6056 KiB
135Elfogadva686ms6196 KiB
136Elfogadva857ms6196 KiB