253142026-02-19 09:23:10Leventusz09Maximális összegű útcpp17Hibás válasz 5/100612ms6268 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 == 0) LN[c] = LX;
                        else LN[c] = ll + A[i][j];
                    }else{
                        if(ll == 0) 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
1Elfogadva1ms508 KiB
2Elfogadva1ms316 KiB
subtask20/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms500 KiB
6Hibás válasz1ms316 KiB
7Hibás válasz1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms500 KiB
11Hibás válasz1ms316 KiB
12Hibás válasz1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva2ms316 KiB
15Elfogadva3ms316 KiB
16Hibás válasz1ms508 KiB
17Elfogadva1ms316 KiB
18Elfogadva3ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms500 KiB
21Hibás válasz3ms532 KiB
22Hibás válasz3ms412 KiB
23Hibás válasz3ms508 KiB
24Elfogadva3ms408 KiB
25Elfogadva3ms316 KiB
26Hibás válasz3ms316 KiB
27Hibás válasz3ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms500 KiB
31Hibás válasz1ms316 KiB
32Hibás válasz1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva2ms316 KiB
35Elfogadva3ms316 KiB
36Hibás válasz1ms508 KiB
37Elfogadva1ms316 KiB
38Elfogadva3ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms500 KiB
41Hibás válasz3ms532 KiB
42Hibás válasz3ms412 KiB
43Hibás válasz3ms508 KiB
44Elfogadva3ms408 KiB
45Elfogadva3ms316 KiB
46Hibás válasz3ms316 KiB
47Hibás válasz3ms316 KiB
48Elfogadva21ms948 KiB
49Elfogadva21ms948 KiB
50Hibás válasz23ms948 KiB
51Elfogadva21ms848 KiB
52Hibás válasz21ms844 KiB
53Hibás válasz23ms820 KiB
54Hibás válasz23ms1176 KiB
55Hibás válasz23ms820 KiB
56Hibás válasz25ms1016 KiB
57Hibás válasz25ms708 KiB
58Elfogadva25ms1180 KiB
59Hibás válasz26ms824 KiB
60Hibás válasz26ms820 KiB
61Hibás válasz27ms952 KiB
subtask55/5
62Elfogadva2ms500 KiB
63Elfogadva2ms316 KiB
64Elfogadva515ms6196 KiB
65Elfogadva521ms6152 KiB
66Elfogadva573ms6120 KiB
67Elfogadva537ms5492 KiB
68Elfogadva597ms6196 KiB
subtask60/12
69Hibás válasz2ms316 KiB
70Elfogadva2ms316 KiB
71Hibás válasz518ms6196 KiB
72Hibás válasz523ms6148 KiB
73Hibás válasz573ms5940 KiB
74Elfogadva538ms5604 KiB
75Hibás válasz597ms6196 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms500 KiB
81Hibás válasz1ms316 KiB
82Hibás válasz1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva2ms316 KiB
85Elfogadva3ms316 KiB
86Hibás válasz1ms508 KiB
87Elfogadva1ms316 KiB
88Elfogadva3ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms500 KiB
91Hibás válasz3ms532 KiB
92Hibás válasz3ms412 KiB
93Hibás válasz3ms508 KiB
94Elfogadva3ms408 KiB
95Elfogadva3ms316 KiB
96Hibás válasz3ms316 KiB
97Hibás válasz3ms316 KiB
98Elfogadva21ms948 KiB
99Elfogadva21ms948 KiB
100Hibás válasz23ms948 KiB
101Elfogadva21ms848 KiB
102Hibás válasz21ms844 KiB
103Hibás válasz23ms820 KiB
104Hibás válasz23ms1176 KiB
105Hibás válasz23ms820 KiB
106Hibás válasz25ms1016 KiB
107Hibás válasz25ms708 KiB
108Elfogadva25ms1180 KiB
109Hibás válasz26ms824 KiB
110Hibás válasz26ms820 KiB
111Hibás válasz27ms952 KiB
112Elfogadva2ms500 KiB
113Elfogadva2ms316 KiB
114Elfogadva515ms6196 KiB
115Elfogadva521ms6152 KiB
116Elfogadva573ms6120 KiB
117Elfogadva537ms5492 KiB
118Elfogadva597ms6196 KiB
119Hibás válasz2ms316 KiB
120Elfogadva2ms316 KiB
121Hibás válasz518ms6196 KiB
122Hibás válasz523ms6148 KiB
123Hibás válasz573ms5940 KiB
124Elfogadva538ms5604 KiB
125Hibás válasz597ms6196 KiB
126Hibás válasz1ms500 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz533ms6104 KiB
129Hibás válasz564ms6244 KiB
130Hibás válasz589ms6116 KiB
131Hibás válasz559ms5628 KiB
132Hibás válasz597ms6196 KiB
133Hibás válasz598ms6224 KiB
134Hibás válasz603ms6124 KiB
135Hibás válasz605ms6196 KiB
136Hibás válasz612ms6268 KiB