251472026-02-18 09:21:03Leventusz09Maximális összegű útcpp17Wrong answer 17/100173ms6272 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] : LN[c] + 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
                    cout << "D" << i <<" " << j <<" "<<c<< endl;
                    #endif
                }
            }
        }

        #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
13Accepted1ms336 KiB
14Accepted1ms316 KiB
15Accepted2ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Wrong answer1ms500 KiB
20Wrong answer1ms500 KiB
21Wrong answer1ms316 KiB
22Wrong answer2ms316 KiB
23Wrong answer2ms316 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Wrong answer2ms316 KiB
27Wrong answer1ms316 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Wrong answer1ms316 KiB
33Accepted1ms336 KiB
34Accepted1ms316 KiB
35Accepted2ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Wrong answer1ms500 KiB
40Wrong answer1ms500 KiB
41Wrong answer1ms316 KiB
42Wrong answer2ms316 KiB
43Wrong answer2ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Wrong answer2ms316 KiB
47Wrong answer1ms316 KiB
48Accepted4ms820 KiB
49Accepted4ms700 KiB
50Wrong answer4ms768 KiB
51Accepted4ms712 KiB
52Wrong answer4ms1016 KiB
53Wrong answer4ms820 KiB
54Wrong answer6ms820 KiB
55Wrong answer6ms832 KiB
56Wrong answer8ms820 KiB
57Wrong answer8ms820 KiB
58Accepted8ms784 KiB
59Accepted8ms736 KiB
60Wrong answer8ms820 KiB
61Wrong answer8ms924 KiB
subtask55/5
62Accepted1ms512 KiB
63Accepted1ms316 KiB
64Accepted96ms6264 KiB
65Accepted97ms6140 KiB
66Accepted153ms5920 KiB
67Accepted143ms5460 KiB
68Accepted162ms6188 KiB
subtask612/12
69Accepted2ms316 KiB
70Accepted2ms316 KiB
71Accepted97ms6196 KiB
72Accepted98ms6196 KiB
73Accepted156ms6040 KiB
74Accepted144ms5496 KiB
75Accepted160ms6196 KiB
subtask70/54
76Wrong answer1ms536 KiB
77Accepted1ms508 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms336 KiB
84Accepted1ms316 KiB
85Accepted2ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Wrong answer1ms500 KiB
90Wrong answer1ms500 KiB
91Wrong answer1ms316 KiB
92Wrong answer2ms316 KiB
93Wrong answer2ms316 KiB
94Accepted1ms316 KiB
95Accepted1ms316 KiB
96Wrong answer2ms316 KiB
97Wrong answer1ms316 KiB
98Accepted4ms820 KiB
99Accepted4ms700 KiB
100Wrong answer4ms768 KiB
101Accepted4ms712 KiB
102Wrong answer4ms1016 KiB
103Wrong answer4ms820 KiB
104Wrong answer6ms820 KiB
105Wrong answer6ms832 KiB
106Wrong answer8ms820 KiB
107Wrong answer8ms820 KiB
108Accepted8ms784 KiB
109Accepted8ms736 KiB
110Wrong answer8ms820 KiB
111Wrong answer8ms924 KiB
112Accepted1ms512 KiB
113Accepted1ms316 KiB
114Accepted96ms6264 KiB
115Accepted97ms6140 KiB
116Accepted153ms5920 KiB
117Accepted143ms5460 KiB
118Accepted162ms6188 KiB
119Accepted2ms316 KiB
120Accepted2ms316 KiB
121Accepted97ms6196 KiB
122Accepted98ms6196 KiB
123Accepted156ms6040 KiB
124Accepted144ms5496 KiB
125Accepted160ms6196 KiB
126Wrong answer1ms508 KiB
127Wrong answer1ms316 KiB
128Wrong answer109ms6272 KiB
129Wrong answer111ms6044 KiB
130Wrong answer167ms5940 KiB
131Wrong answer157ms5624 KiB
132Accepted163ms6060 KiB
133Wrong answer163ms6196 KiB
134Wrong answer166ms6196 KiB
135Wrong answer167ms6052 KiB
136Wrong answer173ms6196 KiB