253032026-02-19 08:39:01Leventusz09Maximális összegű útcpp17Wrong answer 9/100428ms6284 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{
                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
2Accepted1ms508 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
13Accepted1ms500 KiB
14Accepted1ms316 KiB
15Accepted2ms500 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted2ms408 KiB
19Accepted1ms316 KiB
20Accepted1ms440 KiB
21Accepted3ms316 KiB
22Accepted3ms316 KiB
23Accepted3ms392 KiB
24Accepted2ms316 KiB
25Accepted3ms416 KiB
26Accepted3ms528 KiB
27Accepted4ms404 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms500 KiB
34Accepted1ms316 KiB
35Accepted2ms500 KiB
36Wrong answer1ms316 KiB
37Accepted1ms316 KiB
38Accepted2ms408 KiB
39Accepted1ms316 KiB
40Accepted1ms440 KiB
41Accepted3ms316 KiB
42Accepted3ms316 KiB
43Accepted3ms392 KiB
44Accepted2ms316 KiB
45Accepted3ms416 KiB
46Accepted3ms528 KiB
47Accepted4ms404 KiB
48Accepted14ms1004 KiB
49Accepted14ms820 KiB
50Accepted14ms820 KiB
51Accepted14ms1140 KiB
52Accepted16ms832 KiB
53Accepted16ms820 KiB
54Accepted24ms820 KiB
55Accepted23ms820 KiB
56Accepted23ms820 KiB
57Accepted23ms916 KiB
58Accepted17ms820 KiB
59Accepted17ms744 KiB
60Accepted17ms836 KiB
61Accepted24ms1008 KiB
subtask55/5
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted340ms6264 KiB
65Accepted338ms6264 KiB
66Accepted389ms6056 KiB
67Accepted365ms5592 KiB
68Accepted402ms6196 KiB
subtask60/12
69Wrong answer2ms508 KiB
70Accepted2ms508 KiB
71Accepted340ms6196 KiB
72Accepted342ms6196 KiB
73Accepted388ms5888 KiB
74Accepted365ms5532 KiB
75Accepted405ms6196 KiB
subtask70/54
76Accepted1ms512 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms500 KiB
84Accepted1ms316 KiB
85Accepted2ms500 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted2ms408 KiB
89Accepted1ms316 KiB
90Accepted1ms440 KiB
91Accepted3ms316 KiB
92Accepted3ms316 KiB
93Accepted3ms392 KiB
94Accepted2ms316 KiB
95Accepted3ms416 KiB
96Accepted3ms528 KiB
97Accepted4ms404 KiB
98Accepted14ms1004 KiB
99Accepted14ms820 KiB
100Accepted14ms820 KiB
101Accepted14ms1140 KiB
102Accepted16ms832 KiB
103Accepted16ms820 KiB
104Accepted24ms820 KiB
105Accepted23ms820 KiB
106Accepted23ms820 KiB
107Accepted23ms916 KiB
108Accepted17ms820 KiB
109Accepted17ms744 KiB
110Accepted17ms836 KiB
111Accepted24ms1008 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted340ms6264 KiB
115Accepted338ms6264 KiB
116Accepted389ms6056 KiB
117Accepted365ms5592 KiB
118Accepted402ms6196 KiB
119Wrong answer2ms508 KiB
120Accepted2ms508 KiB
121Accepted340ms6196 KiB
122Accepted342ms6196 KiB
123Accepted388ms5888 KiB
124Accepted365ms5532 KiB
125Accepted405ms6196 KiB
126Accepted1ms316 KiB
127Accepted2ms316 KiB
128Wrong answer375ms6232 KiB
129Accepted368ms6136 KiB
130Accepted414ms6032 KiB
131Accepted386ms5608 KiB
132Accepted404ms6172 KiB
133Accepted407ms6196 KiB
134Accepted411ms6088 KiB
135Accepted416ms6224 KiB
136Accepted428ms6284 KiB