250172026-02-17 13:04:38Leventusz09Maximális összegű útcpp17Wrong answer 21/100723ms6264 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){
                    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] = LR[j][c] = A[i][j];
                        }else{
                            LN[c] = LR[j][c] = max(lu, ll) + A[i][j];
                        }
                    }else LN[c] = LR[j][c] = max(lu, ll) + A[i][j];
                }
                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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms336 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
14Accepted2ms316 KiB
15Accepted4ms316 KiB
16Accepted1ms500 KiB
17Accepted1ms332 KiB
18Accepted3ms536 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms332 KiB
21Wrong answer3ms500 KiB
22Wrong answer3ms500 KiB
23Wrong answer3ms316 KiB
24Accepted4ms316 KiB
25Accepted4ms528 KiB
26Wrong answer4ms316 KiB
27Wrong answer4ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted2ms316 KiB
35Accepted4ms316 KiB
36Accepted1ms500 KiB
37Accepted1ms332 KiB
38Accepted3ms536 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms332 KiB
41Wrong answer3ms500 KiB
42Wrong answer3ms500 KiB
43Wrong answer3ms316 KiB
44Accepted4ms316 KiB
45Accepted4ms528 KiB
46Wrong answer4ms316 KiB
47Wrong answer4ms316 KiB
48Accepted27ms948 KiB
49Accepted27ms944 KiB
50Accepted27ms944 KiB
51Accepted27ms780 KiB
52Accepted27ms820 KiB
53Accepted27ms820 KiB
54Wrong answer28ms1012 KiB
55Wrong answer28ms952 KiB
56Wrong answer28ms756 KiB
57Wrong answer28ms1104 KiB
58Accepted28ms820 KiB
59Accepted29ms820 KiB
60Wrong answer29ms952 KiB
61Wrong answer30ms820 KiB
subtask55/5
62Accepted1ms508 KiB
63Accepted1ms316 KiB
64Accepted638ms6264 KiB
65Accepted638ms6196 KiB
66Accepted679ms5904 KiB
67Accepted638ms5516 KiB
68Accepted704ms6192 KiB
subtask612/12
69Accepted2ms500 KiB
70Accepted2ms316 KiB
71Accepted639ms6192 KiB
72Accepted639ms6260 KiB
73Accepted680ms6112 KiB
74Accepted639ms5688 KiB
75Accepted708ms6264 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted2ms316 KiB
85Accepted4ms316 KiB
86Accepted1ms500 KiB
87Accepted1ms332 KiB
88Accepted3ms536 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms332 KiB
91Wrong answer3ms500 KiB
92Wrong answer3ms500 KiB
93Wrong answer3ms316 KiB
94Accepted4ms316 KiB
95Accepted4ms528 KiB
96Wrong answer4ms316 KiB
97Wrong answer4ms316 KiB
98Accepted27ms948 KiB
99Accepted27ms944 KiB
100Accepted27ms944 KiB
101Accepted27ms780 KiB
102Accepted27ms820 KiB
103Accepted27ms820 KiB
104Wrong answer28ms1012 KiB
105Wrong answer28ms952 KiB
106Wrong answer28ms756 KiB
107Wrong answer28ms1104 KiB
108Accepted28ms820 KiB
109Accepted29ms820 KiB
110Wrong answer29ms952 KiB
111Wrong answer30ms820 KiB
112Accepted1ms508 KiB
113Accepted1ms316 KiB
114Accepted638ms6264 KiB
115Accepted638ms6196 KiB
116Accepted679ms5904 KiB
117Accepted638ms5516 KiB
118Accepted704ms6192 KiB
119Accepted2ms500 KiB
120Accepted2ms316 KiB
121Accepted639ms6192 KiB
122Accepted639ms6260 KiB
123Accepted680ms6112 KiB
124Accepted639ms5688 KiB
125Accepted708ms6264 KiB
126Wrong answer1ms316 KiB
127Wrong answer2ms316 KiB
128Wrong answer656ms6140 KiB
129Wrong answer656ms6156 KiB
130Wrong answer698ms6116 KiB
131Wrong answer654ms5684 KiB
132Accepted708ms6196 KiB
133Accepted709ms6240 KiB
134Wrong answer716ms6196 KiB
135Wrong answer717ms6092 KiB
136Wrong answer723ms6212 KiB