251642026-02-18 10:13:26Leventusz09Maximális összegű útcpp17Wrong answer 9/1001.078s6268 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(c != C[i][j] && lu == 0 && ll == 0){
                        LN[c] = 0;
                    }else{
                        LN[c] = max(0LL, 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

*/
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted4ms408 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted4ms536 KiB
19Accepted1ms316 KiB
20Wrong answer1ms316 KiB
21Accepted4ms540 KiB
22Accepted4ms528 KiB
23Accepted4ms596 KiB
24Accepted4ms508 KiB
25Accepted4ms532 KiB
26Accepted4ms348 KiB
27Wrong answer4ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted4ms408 KiB
36Wrong answer1ms316 KiB
37Accepted1ms316 KiB
38Accepted4ms536 KiB
39Accepted1ms316 KiB
40Wrong answer1ms316 KiB
41Accepted4ms540 KiB
42Accepted4ms528 KiB
43Accepted4ms596 KiB
44Accepted4ms508 KiB
45Accepted4ms532 KiB
46Accepted4ms348 KiB
47Wrong answer4ms316 KiB
48Accepted28ms948 KiB
49Accepted28ms972 KiB
50Accepted28ms960 KiB
51Accepted29ms940 KiB
52Accepted29ms948 KiB
53Accepted29ms820 KiB
54Accepted43ms820 KiB
55Accepted43ms948 KiB
56Wrong answer43ms940 KiB
57Wrong answer43ms820 KiB
58Accepted32ms820 KiB
59Accepted32ms948 KiB
60Wrong answer32ms836 KiB
61Wrong answer46ms836 KiB
subtask55/5
62Accepted1ms512 KiB
63Accepted2ms316 KiB
64Accepted703ms6196 KiB
65Accepted703ms6188 KiB
66Accepted745ms6048 KiB
67Accepted700ms5460 KiB
68Accepted776ms6032 KiB
subtask60/12
69Wrong answer1ms316 KiB
70Accepted1ms320 KiB
71Accepted704ms6264 KiB
72Accepted704ms6196 KiB
73Accepted748ms6108 KiB
74Accepted702ms5664 KiB
75Accepted777ms6196 KiB
subtask70/54
76Accepted1ms508 KiB
77Accepted1ms500 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted4ms408 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted4ms536 KiB
89Accepted1ms316 KiB
90Wrong answer1ms316 KiB
91Accepted4ms540 KiB
92Accepted4ms528 KiB
93Accepted4ms596 KiB
94Accepted4ms508 KiB
95Accepted4ms532 KiB
96Accepted4ms348 KiB
97Wrong answer4ms316 KiB
98Accepted28ms948 KiB
99Accepted28ms972 KiB
100Accepted28ms960 KiB
101Accepted29ms940 KiB
102Accepted29ms948 KiB
103Accepted29ms820 KiB
104Accepted43ms820 KiB
105Accepted43ms948 KiB
106Wrong answer43ms940 KiB
107Wrong answer43ms820 KiB
108Accepted32ms820 KiB
109Accepted32ms948 KiB
110Wrong answer32ms836 KiB
111Wrong answer46ms836 KiB
112Accepted1ms512 KiB
113Accepted2ms316 KiB
114Accepted703ms6196 KiB
115Accepted703ms6188 KiB
116Accepted745ms6048 KiB
117Accepted700ms5460 KiB
118Accepted776ms6032 KiB
119Wrong answer1ms316 KiB
120Accepted1ms320 KiB
121Accepted704ms6264 KiB
122Accepted704ms6196 KiB
123Accepted748ms6108 KiB
124Accepted702ms5664 KiB
125Accepted777ms6196 KiB
126Accepted1ms316 KiB
127Wrong answer2ms316 KiB
128Accepted1.006s6268 KiB
129Accepted1.006s6064 KiB
130Wrong answer1.036s5916 KiB
131Wrong answer978ms5656 KiB
132Accepted778ms6268 KiB
133Accepted782ms6264 KiB
134Wrong answer796ms6196 KiB
135Accepted813ms6184 KiB
136Accepted1.078s6200 KiB