249872026-02-17 11:23:44Leventusz09Maximális összegű útcpp17Wrong answer 0/100395ms262144 KiB
#include <iostream>
#define DEBUG false

#define IC for(int c=0; c<5; 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];

    // bal felső sarok
    for(int i=0; i<500; i++) L[0][0][i] = 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;
            }
        }
    }
    
    //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;
            }
        }
    }

    int o=0;
    // 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
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/4
3Wrong answer1ms316 KiB
4Wrong answer1ms316 KiB
5Wrong answer1ms316 KiB
6Wrong answer1ms408 KiB
7Wrong answer1ms316 KiB
subtask30/7
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Wrong answer1ms316 KiB
11Wrong answer1ms408 KiB
12Wrong answer1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms564 KiB
15Accepted3ms2100 KiB
16Accepted1ms508 KiB
17Accepted1ms564 KiB
18Accepted3ms2100 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms564 KiB
21Wrong answer3ms2100 KiB
22Wrong answer2ms1844 KiB
23Wrong answer3ms1964 KiB
24Wrong answer3ms2100 KiB
25Wrong answer3ms2100 KiB
26Wrong answer3ms2100 KiB
27Wrong answer3ms2100 KiB
subtask40/18
28Wrong answer1ms316 KiB
29Wrong answer1ms316 KiB
30Wrong answer1ms316 KiB
31Wrong answer1ms408 KiB
32Wrong answer1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms564 KiB
35Accepted3ms2100 KiB
36Accepted1ms508 KiB
37Accepted1ms564 KiB
38Accepted3ms2100 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms564 KiB
41Wrong answer3ms2100 KiB
42Wrong answer2ms1844 KiB
43Wrong answer3ms1964 KiB
44Wrong answer3ms2100 KiB
45Wrong answer3ms2100 KiB
46Wrong answer3ms2100 KiB
47Wrong answer3ms2100 KiB
48Wrong answer20ms20020 KiB
49Accepted21ms20020 KiB
50Accepted17ms20020 KiB
51Accepted18ms19880 KiB
52Wrong answer17ms19940 KiB
53Wrong answer21ms19976 KiB
54Accepted17ms19992 KiB
55Wrong answer21ms20020 KiB
56Wrong answer19ms18704 KiB
57Wrong answer19ms18744 KiB
58Wrong answer24ms20036 KiB
59Wrong answer25ms20020 KiB
60Wrong answer20ms20020 KiB
61Wrong answer26ms20316 KiB
subtask50/5
62Accepted2ms508 KiB
63Accepted2ms564 KiB
64Runtime error312ms262144 KiB
65Runtime error275ms262144 KiB
66Runtime error381ms262144 KiB
67Runtime error321ms262144 KiB
68Runtime error381ms262144 KiB
subtask60/12
69Accepted2ms388 KiB
70Accepted2ms756 KiB
71Runtime error273ms262144 KiB
72Runtime error270ms262144 KiB
73Runtime error375ms262144 KiB
74Runtime error374ms262144 KiB
75Runtime error338ms262144 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Wrong answer1ms316 KiB
79Wrong answer1ms316 KiB
80Wrong answer1ms316 KiB
81Wrong answer1ms408 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms564 KiB
85Accepted3ms2100 KiB
86Accepted1ms508 KiB
87Accepted1ms564 KiB
88Accepted3ms2100 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms564 KiB
91Wrong answer3ms2100 KiB
92Wrong answer2ms1844 KiB
93Wrong answer3ms1964 KiB
94Wrong answer3ms2100 KiB
95Wrong answer3ms2100 KiB
96Wrong answer3ms2100 KiB
97Wrong answer3ms2100 KiB
98Wrong answer20ms20020 KiB
99Accepted21ms20020 KiB
100Accepted17ms20020 KiB
101Accepted18ms19880 KiB
102Wrong answer17ms19940 KiB
103Wrong answer21ms19976 KiB
104Accepted17ms19992 KiB
105Wrong answer21ms20020 KiB
106Wrong answer19ms18704 KiB
107Wrong answer19ms18744 KiB
108Wrong answer24ms20036 KiB
109Wrong answer25ms20020 KiB
110Wrong answer20ms20020 KiB
111Wrong answer26ms20316 KiB
112Accepted2ms508 KiB
113Accepted2ms564 KiB
114Runtime error312ms262144 KiB
115Runtime error275ms262144 KiB
116Runtime error381ms262144 KiB
117Runtime error321ms262144 KiB
118Runtime error381ms262144 KiB
119Accepted2ms388 KiB
120Accepted2ms756 KiB
121Runtime error273ms262144 KiB
122Runtime error270ms262144 KiB
123Runtime error375ms262144 KiB
124Runtime error374ms262144 KiB
125Runtime error338ms262144 KiB
126Wrong answer1ms316 KiB
127Wrong answer1ms564 KiB
128Runtime error340ms262144 KiB
129Runtime error287ms262144 KiB
130Runtime error344ms262144 KiB
131Runtime error379ms262144 KiB
132Runtime error342ms262144 KiB
133Runtime error340ms262144 KiB
134Runtime error393ms262144 KiB
135Runtime error395ms262144 KiB
136Runtime error352ms262144 KiB