251502026-02-18 09:26:20Leventusz09Maximális összegű útcpp17Wrong answer 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

*/
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms500 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms500 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms336 KiB
14Accepted1ms316 KiB
15Accepted4ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted4ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer4ms536 KiB
22Wrong answer4ms524 KiB
23Wrong answer4ms520 KiB
24Accepted4ms556 KiB
25Accepted4ms316 KiB
26Wrong answer4ms316 KiB
27Wrong answer4ms476 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms500 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms336 KiB
34Accepted1ms316 KiB
35Accepted4ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted4ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer4ms536 KiB
42Wrong answer4ms524 KiB
43Wrong answer4ms520 KiB
44Accepted4ms556 KiB
45Accepted4ms316 KiB
46Wrong answer4ms316 KiB
47Wrong answer4ms476 KiB
48Accepted34ms944 KiB
49Accepted34ms948 KiB
50Accepted34ms944 KiB
51Accepted34ms944 KiB
52Accepted34ms820 KiB
53Accepted34ms1012 KiB
54Wrong answer35ms820 KiB
55Wrong answer35ms820 KiB
56Wrong answer35ms1132 KiB
57Wrong answer35ms820 KiB
58Accepted37ms1056 KiB
59Accepted37ms820 KiB
60Wrong answer37ms1004 KiB
61Wrong answer37ms1140 KiB
subtask55/5
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted815ms6268 KiB
65Accepted815ms6256 KiB
66Accepted851ms5940 KiB
67Accepted800ms5684 KiB
68Accepted883ms6196 KiB
subtask612/12
69Accepted1ms316 KiB
70Accepted2ms316 KiB
71Accepted818ms6196 KiB
72Accepted818ms6196 KiB
73Accepted851ms6044 KiB
74Accepted800ms5608 KiB
75Accepted885ms6196 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms500 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms336 KiB
84Accepted1ms316 KiB
85Accepted4ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted4ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer4ms536 KiB
92Wrong answer4ms524 KiB
93Wrong answer4ms520 KiB
94Accepted4ms556 KiB
95Accepted4ms316 KiB
96Wrong answer4ms316 KiB
97Wrong answer4ms476 KiB
98Accepted34ms944 KiB
99Accepted34ms948 KiB
100Accepted34ms944 KiB
101Accepted34ms944 KiB
102Accepted34ms820 KiB
103Accepted34ms1012 KiB
104Wrong answer35ms820 KiB
105Wrong answer35ms820 KiB
106Wrong answer35ms1132 KiB
107Wrong answer35ms820 KiB
108Accepted37ms1056 KiB
109Accepted37ms820 KiB
110Wrong answer37ms1004 KiB
111Wrong answer37ms1140 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted815ms6268 KiB
115Accepted815ms6256 KiB
116Accepted851ms5940 KiB
117Accepted800ms5684 KiB
118Accepted883ms6196 KiB
119Accepted1ms316 KiB
120Accepted2ms316 KiB
121Accepted818ms6196 KiB
122Accepted818ms6196 KiB
123Accepted851ms6044 KiB
124Accepted800ms5608 KiB
125Accepted885ms6196 KiB
126Wrong answer1ms316 KiB
127Wrong answer2ms508 KiB
128Wrong answer836ms6216 KiB
129Wrong answer833ms6224 KiB
130Wrong answer867ms6048 KiB
131Wrong answer814ms5708 KiB
132Accepted885ms6268 KiB
133Accepted888ms6264 KiB
134Wrong answer893ms6264 KiB
135Wrong answer897ms6196 KiB
136Wrong answer902ms6208 KiB