249932026-02-17 11:31:19Leventusz09Maximális összegű útcpp17Wrong answer 4/100451ms262144 KiB
#include <iostream>
#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];

    // bal felső sarok
    IC L[0][0][c] = 0;
    L[0][0][C[0][0]] = A[0][0];

    // első sor
    for(int i=1; i<M; i++){
        IC{
            if(L[0][i-1][c] > 0 || C[0][i] == c){
                L[0][i][c] = L[0][i-1][c] + A[0][i];
            }else{
                L[0][i][c] = 0;
            }

            if(C[0][i] == c) if(L[0][i][c] > o) o = L[0][i][c];
        }
    }
    
    //első oszlop
    for(int i=1; i<N; i++){
        IC{
            if(L[i-1][0][c] > 0 || C[i][0] == c){
                L[i][0][c] = L[i-1][0][c] + A[i][0];
            }else{
                L[i][0][c] = 0;
            }

            if(C[i][0] == c) if(L[i][0][c] > o) o = L[i][0][c];
        }
    }

    // az összes többi
    for(int i=1; i<N; i++){
        for(int j=1; j<M; j++){
            IC{
                int cu = L[i-1][j][c];
                int cl = L[i][j-1][c];
                if(cu < 0 && cl < 0){
                    if(C[i][j] == c) L[i][j][c] = A[i][j];
                    else L[i][j][c] = max(cu, cl) + A[i][j];
                }
                else L[i][j][c] = max(cu, cl) + A[i][j];

                if(C[i][j] == c) if(L[i][j][c] > o) o = L[i][j][c];
            }
        }
    }
    #if DEBUG
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            IC{
                cout << L[i][j][c] << ".";
            }
            cout << "\t";
        }
        cout << "\n";
    }

    #endif
    cout << o << endl;
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms508 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms508 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms580 KiB
15Accepted4ms3724 KiB
16Accepted1ms316 KiB
17Accepted1ms564 KiB
18Accepted4ms3892 KiB
19Wrong answer1ms316 KiB
20Wrong answer2ms748 KiB
21Wrong answer4ms3788 KiB
22Wrong answer4ms3124 KiB
23Wrong answer4ms3416 KiB
24Wrong answer6ms3724 KiB
25Accepted4ms3892 KiB
26Wrong answer4ms3892 KiB
27Wrong answer4ms3876 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms508 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms580 KiB
35Accepted4ms3724 KiB
36Accepted1ms316 KiB
37Accepted1ms564 KiB
38Accepted4ms3892 KiB
39Wrong answer1ms316 KiB
40Wrong answer2ms748 KiB
41Wrong answer4ms3788 KiB
42Wrong answer4ms3124 KiB
43Wrong answer4ms3416 KiB
44Wrong answer6ms3724 KiB
45Accepted4ms3892 KiB
46Wrong answer4ms3892 KiB
47Wrong answer4ms3876 KiB
48Wrong answer48ms39476 KiB
49Accepted41ms39580 KiB
50Accepted41ms39452 KiB
51Accepted48ms39564 KiB
52Wrong answer48ms39476 KiB
53Wrong answer48ms39476 KiB
54Wrong answer41ms39660 KiB
55Wrong answer41ms39620 KiB
56Wrong answer48ms36916 KiB
57Wrong answer50ms37172 KiB
58Wrong answer43ms39476 KiB
59Wrong answer50ms39476 KiB
60Wrong answer48ms39580 KiB
61Wrong answer43ms39516 KiB
subtask50/5
62Accepted2ms316 KiB
63Accepted2ms564 KiB
64Runtime error381ms262144 KiB
65Runtime error335ms262144 KiB
66Runtime error398ms262144 KiB
67Runtime error435ms262144 KiB
68Runtime error402ms262144 KiB
subtask60/12
69Accepted2ms316 KiB
70Accepted2ms568 KiB
71Runtime error333ms262144 KiB
72Runtime error333ms262144 KiB
73Runtime error435ms262144 KiB
74Runtime error428ms262144 KiB
75Runtime error393ms262144 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms508 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms580 KiB
85Accepted4ms3724 KiB
86Accepted1ms316 KiB
87Accepted1ms564 KiB
88Accepted4ms3892 KiB
89Wrong answer1ms316 KiB
90Wrong answer2ms748 KiB
91Wrong answer4ms3788 KiB
92Wrong answer4ms3124 KiB
93Wrong answer4ms3416 KiB
94Wrong answer6ms3724 KiB
95Accepted4ms3892 KiB
96Wrong answer4ms3892 KiB
97Wrong answer4ms3876 KiB
98Wrong answer48ms39476 KiB
99Accepted41ms39580 KiB
100Accepted41ms39452 KiB
101Accepted48ms39564 KiB
102Wrong answer48ms39476 KiB
103Wrong answer48ms39476 KiB
104Wrong answer41ms39660 KiB
105Wrong answer41ms39620 KiB
106Wrong answer48ms36916 KiB
107Wrong answer50ms37172 KiB
108Wrong answer43ms39476 KiB
109Wrong answer50ms39476 KiB
110Wrong answer48ms39580 KiB
111Wrong answer43ms39516 KiB
112Accepted2ms316 KiB
113Accepted2ms564 KiB
114Runtime error381ms262144 KiB
115Runtime error335ms262144 KiB
116Runtime error398ms262144 KiB
117Runtime error435ms262144 KiB
118Runtime error402ms262144 KiB
119Accepted2ms316 KiB
120Accepted2ms568 KiB
121Runtime error333ms262144 KiB
122Runtime error333ms262144 KiB
123Runtime error435ms262144 KiB
124Runtime error428ms262144 KiB
125Runtime error393ms262144 KiB
126Wrong answer1ms316 KiB
127Wrong answer2ms564 KiB
128Runtime error398ms262144 KiB
129Runtime error395ms262144 KiB
130Runtime error407ms262144 KiB
131Runtime error395ms262144 KiB
132Runtime error444ms262144 KiB
133Runtime error444ms262144 KiB
134Runtime error451ms262144 KiB
135Runtime error402ms262144 KiB
136Runtime error407ms262144 KiB