253002026-02-19 08:33:28Leventusz09Maximális összegű útcpp17Wrong answer 5/100179ms6216 KiB
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long

#define IC for(int c=0; c<6; 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{
                int lu, ll;
                if(i == 0) lu = 0;
                else lu = LR[j][c];
                if(j == 0) ll = 0;
                else ll= LN[c];

                if(c == C[i][j]) LN[c] = max(0LL, max(ll, lu)) + A[i][j];
                else {
                    if(lu == 0){
                        if(ll == 0) LN[c] = 0;
                        else LN[c] = ll + A[i][j];
                    }else{
                        if(ll == 0) LN[c] = lu + 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
        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
subtask20/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Wrong answer1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Wrong answer1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms508 KiB
15Accepted2ms316 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms508 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
21Wrong answer1ms316 KiB
22Wrong answer2ms316 KiB
23Wrong answer1ms316 KiB
24Accepted1ms316 KiB
25Accepted2ms324 KiB
26Accepted2ms316 KiB
27Wrong answer2ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Wrong answer1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms508 KiB
35Accepted2ms316 KiB
36Wrong answer1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms508 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer2ms316 KiB
43Wrong answer1ms316 KiB
44Accepted1ms316 KiB
45Accepted2ms324 KiB
46Accepted2ms316 KiB
47Wrong answer2ms316 KiB
48Accepted4ms924 KiB
49Accepted4ms808 KiB
50Accepted4ms820 KiB
51Accepted4ms820 KiB
52Wrong answer4ms820 KiB
53Accepted4ms756 KiB
54Wrong answer6ms820 KiB
55Wrong answer6ms820 KiB
56Wrong answer9ms1072 KiB
57Wrong answer9ms1020 KiB
58Accepted9ms820 KiB
59Accepted9ms820 KiB
60Wrong answer8ms868 KiB
61Wrong answer8ms952 KiB
subtask55/5
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted98ms6196 KiB
65Accepted100ms6164 KiB
66Accepted157ms5916 KiB
67Accepted146ms5500 KiB
68Accepted163ms6196 KiB
subtask60/12
69Wrong answer2ms316 KiB
70Accepted2ms316 KiB
71Accepted100ms6192 KiB
72Accepted101ms6196 KiB
73Accepted158ms6016 KiB
74Accepted149ms5700 KiB
75Accepted165ms6196 KiB
subtask70/54
76Accepted1ms500 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms508 KiB
85Accepted2ms316 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms508 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms316 KiB
91Wrong answer1ms316 KiB
92Wrong answer2ms316 KiB
93Wrong answer1ms316 KiB
94Accepted1ms316 KiB
95Accepted2ms324 KiB
96Accepted2ms316 KiB
97Wrong answer2ms316 KiB
98Accepted4ms924 KiB
99Accepted4ms808 KiB
100Accepted4ms820 KiB
101Accepted4ms820 KiB
102Wrong answer4ms820 KiB
103Accepted4ms756 KiB
104Wrong answer6ms820 KiB
105Wrong answer6ms820 KiB
106Wrong answer9ms1072 KiB
107Wrong answer9ms1020 KiB
108Accepted9ms820 KiB
109Accepted9ms820 KiB
110Wrong answer8ms868 KiB
111Wrong answer8ms952 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted98ms6196 KiB
115Accepted100ms6164 KiB
116Accepted157ms5916 KiB
117Accepted146ms5500 KiB
118Accepted163ms6196 KiB
119Wrong answer2ms316 KiB
120Accepted2ms316 KiB
121Accepted100ms6192 KiB
122Accepted101ms6196 KiB
123Accepted158ms6016 KiB
124Accepted149ms5700 KiB
125Accepted165ms6196 KiB
126Wrong answer1ms512 KiB
127Wrong answer1ms316 KiB
128Wrong answer114ms6184 KiB
129Wrong answer115ms6044 KiB
130Wrong answer172ms6096 KiB
131Wrong answer162ms5668 KiB
132Accepted166ms6200 KiB
133Accepted166ms6216 KiB
134Accepted171ms6196 KiB
135Wrong answer172ms6056 KiB
136Wrong answer179ms6196 KiB