251502026-02-18 09:26:20Leventusz09Maximális összegű útcpp17Hibás válasz 21/100902ms6268 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){
                    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] : LN[c] + 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
                    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
2Elfogadva1ms316 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms500 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms500 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms336 KiB
14Elfogadva1ms316 KiB
15Elfogadva4ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva4ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz4ms536 KiB
22Hibás válasz4ms524 KiB
23Hibás válasz4ms520 KiB
24Elfogadva4ms556 KiB
25Elfogadva4ms316 KiB
26Hibás válasz4ms316 KiB
27Hibás válasz4ms476 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms500 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms336 KiB
34Elfogadva1ms316 KiB
35Elfogadva4ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva4ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz4ms536 KiB
42Hibás válasz4ms524 KiB
43Hibás válasz4ms520 KiB
44Elfogadva4ms556 KiB
45Elfogadva4ms316 KiB
46Hibás válasz4ms316 KiB
47Hibás válasz4ms476 KiB
48Elfogadva34ms944 KiB
49Elfogadva34ms948 KiB
50Elfogadva34ms944 KiB
51Elfogadva34ms944 KiB
52Elfogadva34ms820 KiB
53Elfogadva34ms1012 KiB
54Hibás válasz35ms820 KiB
55Hibás válasz35ms820 KiB
56Hibás válasz35ms1132 KiB
57Hibás válasz35ms820 KiB
58Elfogadva37ms1056 KiB
59Elfogadva37ms820 KiB
60Hibás válasz37ms1004 KiB
61Hibás válasz37ms1140 KiB
subtask55/5
62Elfogadva1ms316 KiB
63Elfogadva1ms316 KiB
64Elfogadva815ms6268 KiB
65Elfogadva815ms6256 KiB
66Elfogadva851ms5940 KiB
67Elfogadva800ms5684 KiB
68Elfogadva883ms6196 KiB
subtask612/12
69Elfogadva1ms316 KiB
70Elfogadva2ms316 KiB
71Elfogadva818ms6196 KiB
72Elfogadva818ms6196 KiB
73Elfogadva851ms6044 KiB
74Elfogadva800ms5608 KiB
75Elfogadva885ms6196 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms508 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms500 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms336 KiB
84Elfogadva1ms316 KiB
85Elfogadva4ms316 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva4ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Hibás válasz4ms536 KiB
92Hibás válasz4ms524 KiB
93Hibás válasz4ms520 KiB
94Elfogadva4ms556 KiB
95Elfogadva4ms316 KiB
96Hibás válasz4ms316 KiB
97Hibás válasz4ms476 KiB
98Elfogadva34ms944 KiB
99Elfogadva34ms948 KiB
100Elfogadva34ms944 KiB
101Elfogadva34ms944 KiB
102Elfogadva34ms820 KiB
103Elfogadva34ms1012 KiB
104Hibás válasz35ms820 KiB
105Hibás válasz35ms820 KiB
106Hibás válasz35ms1132 KiB
107Hibás válasz35ms820 KiB
108Elfogadva37ms1056 KiB
109Elfogadva37ms820 KiB
110Hibás válasz37ms1004 KiB
111Hibás válasz37ms1140 KiB
112Elfogadva1ms316 KiB
113Elfogadva1ms316 KiB
114Elfogadva815ms6268 KiB
115Elfogadva815ms6256 KiB
116Elfogadva851ms5940 KiB
117Elfogadva800ms5684 KiB
118Elfogadva883ms6196 KiB
119Elfogadva1ms316 KiB
120Elfogadva2ms316 KiB
121Elfogadva818ms6196 KiB
122Elfogadva818ms6196 KiB
123Elfogadva851ms6044 KiB
124Elfogadva800ms5608 KiB
125Elfogadva885ms6196 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz2ms508 KiB
128Hibás válasz836ms6216 KiB
129Hibás válasz833ms6224 KiB
130Hibás válasz867ms6048 KiB
131Hibás válasz814ms5708 KiB
132Elfogadva885ms6268 KiB
133Elfogadva888ms6264 KiB
134Hibás válasz893ms6264 KiB
135Hibás válasz897ms6196 KiB
136Hibás válasz902ms6208 KiB