253142026-02-19 09:23:10Leventusz09Maximális összegű útcpp17Wrong answer 5/100612ms6268 KiB
#include <limits.h>
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long
#define LX LLONG_MIN

#if DEBUG
#define IC for(int c=0; c<2; c++)
#else
#define IC for(int c=0; c<500; c++)
#endif

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 = LX;
                else lu = LR[j][c];
                if(j == 0) ll = LX;
                else ll= LN[c];

                if(c == C[i][j]) LN[c] = max(0LL, max(ll, lu)) + A[i][j];
                else {
                    if(lu == LX){
                        if(ll == 0) LN[c] = LX;
                        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
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms500 KiB
6Wrong answer1ms316 KiB
7Wrong answer1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms500 KiB
11Wrong answer1ms316 KiB
12Wrong answer1ms316 KiB
13Accepted1ms316 KiB
14Accepted2ms316 KiB
15Accepted3ms316 KiB
16Wrong answer1ms508 KiB
17Accepted1ms316 KiB
18Accepted3ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms500 KiB
21Wrong answer3ms532 KiB
22Wrong answer3ms412 KiB
23Wrong answer3ms508 KiB
24Accepted3ms408 KiB
25Accepted3ms316 KiB
26Wrong answer3ms316 KiB
27Wrong answer3ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms500 KiB
31Wrong answer1ms316 KiB
32Wrong answer1ms316 KiB
33Accepted1ms316 KiB
34Accepted2ms316 KiB
35Accepted3ms316 KiB
36Wrong answer1ms508 KiB
37Accepted1ms316 KiB
38Accepted3ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms500 KiB
41Wrong answer3ms532 KiB
42Wrong answer3ms412 KiB
43Wrong answer3ms508 KiB
44Accepted3ms408 KiB
45Accepted3ms316 KiB
46Wrong answer3ms316 KiB
47Wrong answer3ms316 KiB
48Accepted21ms948 KiB
49Accepted21ms948 KiB
50Wrong answer23ms948 KiB
51Accepted21ms848 KiB
52Wrong answer21ms844 KiB
53Wrong answer23ms820 KiB
54Wrong answer23ms1176 KiB
55Wrong answer23ms820 KiB
56Wrong answer25ms1016 KiB
57Wrong answer25ms708 KiB
58Accepted25ms1180 KiB
59Wrong answer26ms824 KiB
60Wrong answer26ms820 KiB
61Wrong answer27ms952 KiB
subtask55/5
62Accepted2ms500 KiB
63Accepted2ms316 KiB
64Accepted515ms6196 KiB
65Accepted521ms6152 KiB
66Accepted573ms6120 KiB
67Accepted537ms5492 KiB
68Accepted597ms6196 KiB
subtask60/12
69Wrong answer2ms316 KiB
70Accepted2ms316 KiB
71Wrong answer518ms6196 KiB
72Wrong answer523ms6148 KiB
73Wrong answer573ms5940 KiB
74Accepted538ms5604 KiB
75Wrong answer597ms6196 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms500 KiB
81Wrong answer1ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Accepted2ms316 KiB
85Accepted3ms316 KiB
86Wrong answer1ms508 KiB
87Accepted1ms316 KiB
88Accepted3ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms500 KiB
91Wrong answer3ms532 KiB
92Wrong answer3ms412 KiB
93Wrong answer3ms508 KiB
94Accepted3ms408 KiB
95Accepted3ms316 KiB
96Wrong answer3ms316 KiB
97Wrong answer3ms316 KiB
98Accepted21ms948 KiB
99Accepted21ms948 KiB
100Wrong answer23ms948 KiB
101Accepted21ms848 KiB
102Wrong answer21ms844 KiB
103Wrong answer23ms820 KiB
104Wrong answer23ms1176 KiB
105Wrong answer23ms820 KiB
106Wrong answer25ms1016 KiB
107Wrong answer25ms708 KiB
108Accepted25ms1180 KiB
109Wrong answer26ms824 KiB
110Wrong answer26ms820 KiB
111Wrong answer27ms952 KiB
112Accepted2ms500 KiB
113Accepted2ms316 KiB
114Accepted515ms6196 KiB
115Accepted521ms6152 KiB
116Accepted573ms6120 KiB
117Accepted537ms5492 KiB
118Accepted597ms6196 KiB
119Wrong answer2ms316 KiB
120Accepted2ms316 KiB
121Wrong answer518ms6196 KiB
122Wrong answer523ms6148 KiB
123Wrong answer573ms5940 KiB
124Accepted538ms5604 KiB
125Wrong answer597ms6196 KiB
126Wrong answer1ms500 KiB
127Wrong answer2ms316 KiB
128Wrong answer533ms6104 KiB
129Wrong answer564ms6244 KiB
130Wrong answer589ms6116 KiB
131Wrong answer559ms5628 KiB
132Wrong answer597ms6196 KiB
133Wrong answer598ms6224 KiB
134Wrong answer603ms6124 KiB
135Wrong answer605ms6196 KiB
136Wrong answer612ms6268 KiB