251802026-02-18 11:39:04Leventusz09Maximális összegű útcpp17Hibás válasz 21/100486ms6204 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){
                    // első oszlop
                    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(c == C[i][j]){
                        LN[c] = max(0LL, max(lu, ll)) + A[i][j];
                    }else{
                        LN[c] = max(lu, ll) + A[i][j];
                    }
                    /*
                    if(c != C[i][j] && lu == 0 && ll == 0){
                        LN[c] = 0;
                    }else{
                        if(c == C[i][j]){
                            LN[c] = max(0LL, max(lu, ll)) + 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
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva2ms504 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva2ms504 KiB
11Elfogadva1ms508 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms332 KiB
14Elfogadva1ms500 KiB
15Elfogadva3ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva2ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz3ms508 KiB
22Hibás válasz3ms316 KiB
23Hibás válasz3ms316 KiB
24Elfogadva3ms552 KiB
25Elfogadva3ms408 KiB
26Hibás válasz3ms316 KiB
27Hibás válasz3ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva2ms504 KiB
31Elfogadva1ms508 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms332 KiB
34Elfogadva1ms500 KiB
35Elfogadva3ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz3ms508 KiB
42Hibás válasz3ms316 KiB
43Hibás válasz3ms316 KiB
44Elfogadva3ms552 KiB
45Elfogadva3ms408 KiB
46Hibás válasz3ms316 KiB
47Hibás válasz3ms316 KiB
48Elfogadva17ms820 KiB
49Elfogadva17ms944 KiB
50Elfogadva17ms952 KiB
51Elfogadva17ms944 KiB
52Elfogadva17ms944 KiB
53Elfogadva17ms948 KiB
54Hibás válasz17ms812 KiB
55Hibás válasz17ms944 KiB
56Hibás válasz20ms820 KiB
57Hibás válasz19ms820 KiB
58Elfogadva20ms820 KiB
59Elfogadva20ms828 KiB
60Hibás válasz19ms820 KiB
61Hibás válasz20ms948 KiB
subtask55/5
62Elfogadva1ms508 KiB
63Elfogadva1ms316 KiB
64Elfogadva400ms6196 KiB
65Elfogadva398ms6056 KiB
66Elfogadva449ms5868 KiB
67Elfogadva423ms5708 KiB
68Elfogadva469ms6192 KiB
subtask612/12
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva400ms6196 KiB
72Elfogadva402ms6192 KiB
73Elfogadva451ms5940 KiB
74Elfogadva423ms5684 KiB
75Elfogadva469ms6052 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva2ms504 KiB
81Elfogadva1ms508 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms332 KiB
84Elfogadva1ms500 KiB
85Elfogadva3ms316 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva2ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Hibás válasz3ms508 KiB
92Hibás válasz3ms316 KiB
93Hibás válasz3ms316 KiB
94Elfogadva3ms552 KiB
95Elfogadva3ms408 KiB
96Hibás válasz3ms316 KiB
97Hibás válasz3ms316 KiB
98Elfogadva17ms820 KiB
99Elfogadva17ms944 KiB
100Elfogadva17ms952 KiB
101Elfogadva17ms944 KiB
102Elfogadva17ms944 KiB
103Elfogadva17ms948 KiB
104Hibás válasz17ms812 KiB
105Hibás válasz17ms944 KiB
106Hibás válasz20ms820 KiB
107Hibás válasz19ms820 KiB
108Elfogadva20ms820 KiB
109Elfogadva20ms828 KiB
110Hibás válasz19ms820 KiB
111Hibás válasz20ms948 KiB
112Elfogadva1ms508 KiB
113Elfogadva1ms316 KiB
114Elfogadva400ms6196 KiB
115Elfogadva398ms6056 KiB
116Elfogadva449ms5868 KiB
117Elfogadva423ms5708 KiB
118Elfogadva469ms6192 KiB
119Elfogadva1ms316 KiB
120Elfogadva1ms316 KiB
121Elfogadva400ms6196 KiB
122Elfogadva402ms6192 KiB
123Elfogadva451ms5940 KiB
124Elfogadva423ms5684 KiB
125Elfogadva469ms6052 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz416ms6104 KiB
129Hibás válasz419ms6164 KiB
130Hibás válasz465ms5940 KiB
131Hibás válasz441ms5468 KiB
132Elfogadva470ms6196 KiB
133Elfogadva470ms6192 KiB
134Hibás válasz477ms6180 KiB
135Hibás válasz476ms6092 KiB
136Hibás válasz486ms6204 KiB