250252026-02-17 13:55:31Leventusz09Maximális összegű útcpp17Hibás válasz 5/100201ms6268 KiB
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long

#define IC for(int c=0; c<9; 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
1Elfogadva1ms316 KiB
2Elfogadva1ms508 KiB
subtask20/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms544 KiB
7Hibás válasz1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms544 KiB
12Hibás válasz1ms316 KiB
13Elfogadva1ms536 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Hibás válasz1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms316 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
24Elfogadva2ms404 KiB
25Elfogadva2ms408 KiB
26Elfogadva2ms408 KiB
27Hibás válasz2ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms544 KiB
32Hibás válasz1ms316 KiB
33Elfogadva1ms536 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Hibás válasz1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms316 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
44Elfogadva2ms404 KiB
45Elfogadva2ms408 KiB
46Elfogadva2ms408 KiB
47Hibás válasz2ms316 KiB
48Elfogadva6ms1136 KiB
49Elfogadva6ms820 KiB
50Elfogadva6ms820 KiB
51Elfogadva6ms824 KiB
52Elfogadva6ms820 KiB
53Elfogadva6ms928 KiB
54Hibás válasz6ms836 KiB
55Hibás válasz6ms820 KiB
56Hibás válasz8ms728 KiB
57Hibás válasz8ms800 KiB
58Elfogadva8ms748 KiB
59Elfogadva8ms956 KiB
60Hibás válasz8ms948 KiB
61Hibás válasz8ms820 KiB
subtask55/5
62Elfogadva1ms372 KiB
63Elfogadva1ms316 KiB
64Elfogadva109ms6268 KiB
65Elfogadva108ms6220 KiB
66Elfogadva174ms6056 KiB
67Elfogadva165ms5688 KiB
68Elfogadva182ms6196 KiB
subtask60/12
69Hibás válasz2ms316 KiB
70Elfogadva1ms508 KiB
71Elfogadva111ms6212 KiB
72Elfogadva112ms6196 KiB
73Elfogadva177ms5940 KiB
74Elfogadva165ms5680 KiB
75Elfogadva182ms6196 KiB
subtask70/54
76Elfogadva1ms500 KiB
77Elfogadva1ms500 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms544 KiB
82Hibás válasz1ms316 KiB
83Elfogadva1ms536 KiB
84Elfogadva1ms316 KiB
85Elfogadva1ms316 KiB
86Hibás válasz1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 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
94Elfogadva2ms404 KiB
95Elfogadva2ms408 KiB
96Elfogadva2ms408 KiB
97Hibás válasz2ms316 KiB
98Elfogadva6ms1136 KiB
99Elfogadva6ms820 KiB
100Elfogadva6ms820 KiB
101Elfogadva6ms824 KiB
102Elfogadva6ms820 KiB
103Elfogadva6ms928 KiB
104Hibás válasz6ms836 KiB
105Hibás válasz6ms820 KiB
106Hibás válasz8ms728 KiB
107Hibás válasz8ms800 KiB
108Elfogadva8ms748 KiB
109Elfogadva8ms956 KiB
110Hibás válasz8ms948 KiB
111Hibás válasz8ms820 KiB
112Elfogadva1ms372 KiB
113Elfogadva1ms316 KiB
114Elfogadva109ms6268 KiB
115Elfogadva108ms6220 KiB
116Elfogadva174ms6056 KiB
117Elfogadva165ms5688 KiB
118Elfogadva182ms6196 KiB
119Hibás válasz2ms316 KiB
120Elfogadva1ms508 KiB
121Elfogadva111ms6212 KiB
122Elfogadva112ms6196 KiB
123Elfogadva177ms5940 KiB
124Elfogadva165ms5680 KiB
125Elfogadva182ms6196 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz128ms6068 KiB
129Hibás válasz128ms6196 KiB
130Hibás válasz193ms6080 KiB
131Hibás válasz180ms5556 KiB
132Elfogadva185ms6196 KiB
133Elfogadva187ms6028 KiB
134Hibás válasz190ms6196 KiB
135Hibás válasz192ms6196 KiB
136Hibás válasz201ms6196 KiB