251542026-02-18 09:43:38Leventusz09Maximális összegű útcpp17Wrong answer 0/100192ms6260 KiB
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long

#define IC for(int c=0; c<2; 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{
                if(i == 0 && j == 0){
                    // bal felső sarok
                    LN[c] = 0;
                    if(C[0][0] == c) LN[c] = A[0][0];
                    LR[0][c] = LN[c];
                }else
                if(i == 0){
                    // első sor
                    if(LN[c] > 0){
                        LN[c] += A[i][j];
                    }else{
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }
                    
                    LR[j][c] = LN[c];
                }
                else if(j==0){
                    if(LR[0][c] > 0){
                        LN[c] = LR[0][c] + A[i][j];
                    }else{
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }

                    LR[j][c] = LN[c];
                }else{
                    int lu = LR[j][c];
                    int ll = LN[c];
                    if(lu < 0 && ll < 0){
                        if(C[i][j] == c){
                            LN[c] = A[i][j];
                        }else{
                            LN[c] = max(lu, ll) + A[i][j];
                        }
                    //}else LN[c] = C[i][j] == c ? max(lu, ll) + A[i][j] : 0;
                    }else if(lu == 0 || ll == 0){
                        LN[c] = C[i][j] == c ? A[i][j] : 0;
                    }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
1Wrong answer1ms316 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
13Wrong answer1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Wrong answer1ms508 KiB
17Accepted1ms316 KiB
18Wrong answer1ms316 KiB
19Wrong answer1ms352 KiB
20Wrong answer1ms316 KiB
21Wrong answer1ms408 KiB
22Wrong answer1ms316 KiB
23Wrong answer2ms500 KiB
24Accepted2ms316 KiB
25Wrong answer2ms316 KiB
26Wrong answer2ms508 KiB
27Wrong answer2ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Wrong answer1ms316 KiB
33Wrong answer1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Wrong answer1ms508 KiB
37Accepted1ms316 KiB
38Wrong answer1ms316 KiB
39Wrong answer1ms352 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms408 KiB
42Wrong answer1ms316 KiB
43Wrong answer2ms500 KiB
44Accepted2ms316 KiB
45Wrong answer2ms316 KiB
46Wrong answer2ms508 KiB
47Wrong answer2ms316 KiB
48Wrong answer4ms820 KiB
49Accepted4ms820 KiB
50Wrong answer4ms820 KiB
51Wrong answer4ms820 KiB
52Wrong answer4ms740 KiB
53Wrong answer4ms820 KiB
54Wrong answer6ms928 KiB
55Wrong answer6ms772 KiB
56Wrong answer8ms820 KiB
57Wrong answer8ms820 KiB
58Accepted8ms820 KiB
59Accepted8ms948 KiB
60Wrong answer8ms920 KiB
61Wrong answer8ms820 KiB
subtask50/5
62Wrong answer1ms316 KiB
63Accepted1ms316 KiB
64Accepted101ms6072 KiB
65Accepted101ms6244 KiB
66Accepted168ms5944 KiB
67Accepted158ms5684 KiB
68Accepted174ms6192 KiB
subtask60/12
69Wrong answer1ms316 KiB
70Accepted1ms508 KiB
71Wrong answer104ms6196 KiB
72Wrong answer105ms6040 KiB
73Wrong answer170ms5984 KiB
74Accepted159ms5552 KiB
75Wrong answer178ms6196 KiB
subtask70/54
76Wrong answer1ms316 KiB
77Accepted1ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Wrong answer1ms316 KiB
83Wrong answer1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Wrong answer1ms508 KiB
87Accepted1ms316 KiB
88Wrong answer1ms316 KiB
89Wrong answer1ms352 KiB
90Wrong answer1ms316 KiB
91Wrong answer1ms408 KiB
92Wrong answer1ms316 KiB
93Wrong answer2ms500 KiB
94Accepted2ms316 KiB
95Wrong answer2ms316 KiB
96Wrong answer2ms508 KiB
97Wrong answer2ms316 KiB
98Wrong answer4ms820 KiB
99Accepted4ms820 KiB
100Wrong answer4ms820 KiB
101Wrong answer4ms820 KiB
102Wrong answer4ms740 KiB
103Wrong answer4ms820 KiB
104Wrong answer6ms928 KiB
105Wrong answer6ms772 KiB
106Wrong answer8ms820 KiB
107Wrong answer8ms820 KiB
108Accepted8ms820 KiB
109Accepted8ms948 KiB
110Wrong answer8ms920 KiB
111Wrong answer8ms820 KiB
112Wrong answer1ms316 KiB
113Accepted1ms316 KiB
114Accepted101ms6072 KiB
115Accepted101ms6244 KiB
116Accepted168ms5944 KiB
117Accepted158ms5684 KiB
118Accepted174ms6192 KiB
119Wrong answer1ms316 KiB
120Accepted1ms508 KiB
121Wrong answer104ms6196 KiB
122Wrong answer105ms6040 KiB
123Wrong answer170ms5984 KiB
124Accepted159ms5552 KiB
125Wrong answer178ms6196 KiB
126Wrong answer1ms316 KiB
127Wrong answer1ms316 KiB
128Wrong answer119ms6260 KiB
129Wrong answer116ms6160 KiB
130Wrong answer184ms5924 KiB
131Wrong answer174ms5464 KiB
132Wrong answer180ms6196 KiB
133Wrong answer178ms6236 KiB
134Wrong answer185ms6240 KiB
135Wrong answer184ms6192 KiB
136Wrong answer192ms6208 KiB