253002026-02-19 08:33:28Leventusz09Maximális összegű útcpp17Hibás válasz 5/100179ms6216 KiB
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long

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

                if(c == C[i][j]) LN[c] = max(0LL, max(ll, lu)) + A[i][j];
                else {
                    if(lu == 0){
                        if(ll == 0) LN[c] = 0;
                        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
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask20/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Hibás válasz1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Hibás válasz1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms508 KiB
15Elfogadva2ms316 KiB
16Hibás válasz1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms508 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz1ms316 KiB
22Hibás válasz2ms316 KiB
23Hibás válasz1ms316 KiB
24Elfogadva1ms316 KiB
25Elfogadva2ms324 KiB
26Elfogadva2ms316 KiB
27Hibás válasz2ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Hibás válasz1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms508 KiB
35Elfogadva2ms316 KiB
36Hibás válasz1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms508 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz1ms316 KiB
42Hibás válasz2ms316 KiB
43Hibás válasz1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva2ms324 KiB
46Elfogadva2ms316 KiB
47Hibás válasz2ms316 KiB
48Elfogadva4ms924 KiB
49Elfogadva4ms808 KiB
50Elfogadva4ms820 KiB
51Elfogadva4ms820 KiB
52Hibás válasz4ms820 KiB
53Elfogadva4ms756 KiB
54Hibás válasz6ms820 KiB
55Hibás válasz6ms820 KiB
56Hibás válasz9ms1072 KiB
57Hibás válasz9ms1020 KiB
58Elfogadva9ms820 KiB
59Elfogadva9ms820 KiB
60Hibás válasz8ms868 KiB
61Hibás válasz8ms952 KiB
subtask55/5
62Elfogadva1ms316 KiB
63Elfogadva1ms316 KiB
64Elfogadva98ms6196 KiB
65Elfogadva100ms6164 KiB
66Elfogadva157ms5916 KiB
67Elfogadva146ms5500 KiB
68Elfogadva163ms6196 KiB
subtask60/12
69Hibás válasz2ms316 KiB
70Elfogadva2ms316 KiB
71Elfogadva100ms6192 KiB
72Elfogadva101ms6196 KiB
73Elfogadva158ms6016 KiB
74Elfogadva149ms5700 KiB
75Elfogadva165ms6196 KiB
subtask70/54
76Elfogadva1ms500 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Hibás válasz1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms508 KiB
85Elfogadva2ms316 KiB
86Hibás válasz1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms508 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Hibás válasz1ms316 KiB
92Hibás válasz2ms316 KiB
93Hibás válasz1ms316 KiB
94Elfogadva1ms316 KiB
95Elfogadva2ms324 KiB
96Elfogadva2ms316 KiB
97Hibás válasz2ms316 KiB
98Elfogadva4ms924 KiB
99Elfogadva4ms808 KiB
100Elfogadva4ms820 KiB
101Elfogadva4ms820 KiB
102Hibás válasz4ms820 KiB
103Elfogadva4ms756 KiB
104Hibás válasz6ms820 KiB
105Hibás válasz6ms820 KiB
106Hibás válasz9ms1072 KiB
107Hibás válasz9ms1020 KiB
108Elfogadva9ms820 KiB
109Elfogadva9ms820 KiB
110Hibás válasz8ms868 KiB
111Hibás válasz8ms952 KiB
112Elfogadva1ms316 KiB
113Elfogadva1ms316 KiB
114Elfogadva98ms6196 KiB
115Elfogadva100ms6164 KiB
116Elfogadva157ms5916 KiB
117Elfogadva146ms5500 KiB
118Elfogadva163ms6196 KiB
119Hibás válasz2ms316 KiB
120Elfogadva2ms316 KiB
121Elfogadva100ms6192 KiB
122Elfogadva101ms6196 KiB
123Elfogadva158ms6016 KiB
124Elfogadva149ms5700 KiB
125Elfogadva165ms6196 KiB
126Hibás válasz1ms512 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz114ms6184 KiB
129Hibás válasz115ms6044 KiB
130Hibás válasz172ms6096 KiB
131Hibás válasz162ms5668 KiB
132Elfogadva166ms6200 KiB
133Elfogadva166ms6216 KiB
134Elfogadva171ms6196 KiB
135Hibás válasz172ms6056 KiB
136Hibás válasz179ms6196 KiB