253152026-02-19 09:27:58Leventusz09Maximális összegű útcpp17Elfogadva 100/100476ms6224 KiB
#include <limits.h>
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long
#define LX LLONG_MIN

#if DEBUG
#define IC for(int c=0; c<2; c++)
#else
#define IC for(int c=0; c<500; c++)
#endif

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{
                int lu, ll;
                if(i == 0) lu = LX;
                else lu = LR[j][c];
                if(j == 0) ll = LX;
                else ll= LN[c];

                if(c == C[i][j]) LN[c] = max(0LL, max(ll, lu)) + A[i][j];
                else {
                    if(lu == LX){
                        if(ll == LX) LN[c] = LX;
                        else LN[c] = ll + A[i][j];
                    }else{
                        if(ll == LX) LN[c] = lu + A[i][j];
                        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
1Elfogadva1ms500 KiB
2Elfogadva1ms316 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva2ms316 KiB
5Elfogadva1ms376 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask37/7
8Elfogadva1ms316 KiB
9Elfogadva2ms316 KiB
10Elfogadva1ms376 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva2ms316 KiB
16Elfogadva1ms508 KiB
17Elfogadva1ms316 KiB
18Elfogadva2ms316 KiB
19Elfogadva1ms388 KiB
20Elfogadva1ms316 KiB
21Elfogadva4ms536 KiB
22Elfogadva3ms540 KiB
23Elfogadva3ms316 KiB
24Elfogadva3ms316 KiB
25Elfogadva3ms316 KiB
26Elfogadva3ms316 KiB
27Elfogadva4ms508 KiB
subtask418/18
28Elfogadva1ms316 KiB
29Elfogadva2ms316 KiB
30Elfogadva1ms376 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva2ms316 KiB
36Elfogadva1ms508 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms316 KiB
39Elfogadva1ms388 KiB
40Elfogadva1ms316 KiB
41Elfogadva4ms536 KiB
42Elfogadva3ms540 KiB
43Elfogadva3ms316 KiB
44Elfogadva3ms316 KiB
45Elfogadva3ms316 KiB
46Elfogadva3ms316 KiB
47Elfogadva4ms508 KiB
48Elfogadva17ms804 KiB
49Elfogadva17ms820 KiB
50Elfogadva17ms916 KiB
51Elfogadva17ms944 KiB
52Elfogadva17ms820 KiB
53Elfogadva17ms1124 KiB
54Elfogadva21ms820 KiB
55Elfogadva21ms820 KiB
56Elfogadva23ms820 KiB
57Elfogadva23ms820 KiB
58Elfogadva20ms948 KiB
59Elfogadva19ms820 KiB
60Elfogadva20ms1012 KiB
61Elfogadva25ms1160 KiB
subtask55/5
62Elfogadva2ms316 KiB
63Elfogadva2ms316 KiB
64Elfogadva402ms6188 KiB
65Elfogadva402ms6196 KiB
66Elfogadva449ms5940 KiB
67Elfogadva423ms5684 KiB
68Elfogadva467ms6196 KiB
subtask612/12
69Elfogadva1ms508 KiB
70Elfogadva2ms508 KiB
71Elfogadva404ms6196 KiB
72Elfogadva404ms6120 KiB
73Elfogadva451ms5936 KiB
74Elfogadva423ms5636 KiB
75Elfogadva469ms6196 KiB
subtask754/54
76Elfogadva2ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva2ms316 KiB
80Elfogadva1ms376 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms316 KiB
85Elfogadva2ms316 KiB
86Elfogadva1ms508 KiB
87Elfogadva1ms316 KiB
88Elfogadva2ms316 KiB
89Elfogadva1ms388 KiB
90Elfogadva1ms316 KiB
91Elfogadva4ms536 KiB
92Elfogadva3ms540 KiB
93Elfogadva3ms316 KiB
94Elfogadva3ms316 KiB
95Elfogadva3ms316 KiB
96Elfogadva3ms316 KiB
97Elfogadva4ms508 KiB
98Elfogadva17ms804 KiB
99Elfogadva17ms820 KiB
100Elfogadva17ms916 KiB
101Elfogadva17ms944 KiB
102Elfogadva17ms820 KiB
103Elfogadva17ms1124 KiB
104Elfogadva21ms820 KiB
105Elfogadva21ms820 KiB
106Elfogadva23ms820 KiB
107Elfogadva23ms820 KiB
108Elfogadva20ms948 KiB
109Elfogadva19ms820 KiB
110Elfogadva20ms1012 KiB
111Elfogadva25ms1160 KiB
112Elfogadva2ms316 KiB
113Elfogadva2ms316 KiB
114Elfogadva402ms6188 KiB
115Elfogadva402ms6196 KiB
116Elfogadva449ms5940 KiB
117Elfogadva423ms5684 KiB
118Elfogadva467ms6196 KiB
119Elfogadva1ms508 KiB
120Elfogadva2ms508 KiB
121Elfogadva404ms6196 KiB
122Elfogadva404ms6120 KiB
123Elfogadva451ms5936 KiB
124Elfogadva423ms5636 KiB
125Elfogadva469ms6196 KiB
126Elfogadva1ms508 KiB
127Elfogadva1ms316 KiB
128Elfogadva368ms6064 KiB
129Elfogadva368ms6192 KiB
130Elfogadva418ms6048 KiB
131Elfogadva395ms5688 KiB
132Elfogadva470ms6224 KiB
133Elfogadva472ms6212 KiB
134Elfogadva476ms6196 KiB
135Elfogadva476ms6084 KiB
136Elfogadva437ms6196 KiB