250172026-02-17 13:04:38Leventusz09Maximális összegű útcpp17Hibás válasz 21/100723ms6264 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{
                if(i == 0 && j == 0){
                    LN[c] = 0;
                    if(C[0][0] == c) LN[c] = A[0][0];
                    LR[0][c] = LN[c];
                }else
                if(i == 0){
                    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] = LR[j][c] = A[i][j];
                        }else{
                            LN[c] = LR[j][c] = max(lu, ll) + A[i][j];
                        }
                    }else LN[c] = LR[j][c] = max(lu, ll) + A[i][j];
                }
                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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms336 KiB
2Elfogadva1ms316 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva2ms316 KiB
15Elfogadva4ms316 KiB
16Elfogadva1ms500 KiB
17Elfogadva1ms332 KiB
18Elfogadva3ms536 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms332 KiB
21Hibás válasz3ms500 KiB
22Hibás válasz3ms500 KiB
23Hibás válasz3ms316 KiB
24Elfogadva4ms316 KiB
25Elfogadva4ms528 KiB
26Hibás válasz4ms316 KiB
27Hibás válasz4ms316 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva2ms316 KiB
35Elfogadva4ms316 KiB
36Elfogadva1ms500 KiB
37Elfogadva1ms332 KiB
38Elfogadva3ms536 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms332 KiB
41Hibás válasz3ms500 KiB
42Hibás válasz3ms500 KiB
43Hibás válasz3ms316 KiB
44Elfogadva4ms316 KiB
45Elfogadva4ms528 KiB
46Hibás válasz4ms316 KiB
47Hibás válasz4ms316 KiB
48Elfogadva27ms948 KiB
49Elfogadva27ms944 KiB
50Elfogadva27ms944 KiB
51Elfogadva27ms780 KiB
52Elfogadva27ms820 KiB
53Elfogadva27ms820 KiB
54Hibás válasz28ms1012 KiB
55Hibás válasz28ms952 KiB
56Hibás válasz28ms756 KiB
57Hibás válasz28ms1104 KiB
58Elfogadva28ms820 KiB
59Elfogadva29ms820 KiB
60Hibás válasz29ms952 KiB
61Hibás válasz30ms820 KiB
subtask55/5
62Elfogadva1ms508 KiB
63Elfogadva1ms316 KiB
64Elfogadva638ms6264 KiB
65Elfogadva638ms6196 KiB
66Elfogadva679ms5904 KiB
67Elfogadva638ms5516 KiB
68Elfogadva704ms6192 KiB
subtask612/12
69Elfogadva2ms500 KiB
70Elfogadva2ms316 KiB
71Elfogadva639ms6192 KiB
72Elfogadva639ms6260 KiB
73Elfogadva680ms6112 KiB
74Elfogadva639ms5688 KiB
75Elfogadva708ms6264 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva2ms316 KiB
85Elfogadva4ms316 KiB
86Elfogadva1ms500 KiB
87Elfogadva1ms332 KiB
88Elfogadva3ms536 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms332 KiB
91Hibás válasz3ms500 KiB
92Hibás válasz3ms500 KiB
93Hibás válasz3ms316 KiB
94Elfogadva4ms316 KiB
95Elfogadva4ms528 KiB
96Hibás válasz4ms316 KiB
97Hibás válasz4ms316 KiB
98Elfogadva27ms948 KiB
99Elfogadva27ms944 KiB
100Elfogadva27ms944 KiB
101Elfogadva27ms780 KiB
102Elfogadva27ms820 KiB
103Elfogadva27ms820 KiB
104Hibás válasz28ms1012 KiB
105Hibás válasz28ms952 KiB
106Hibás válasz28ms756 KiB
107Hibás válasz28ms1104 KiB
108Elfogadva28ms820 KiB
109Elfogadva29ms820 KiB
110Hibás válasz29ms952 KiB
111Hibás válasz30ms820 KiB
112Elfogadva1ms508 KiB
113Elfogadva1ms316 KiB
114Elfogadva638ms6264 KiB
115Elfogadva638ms6196 KiB
116Elfogadva679ms5904 KiB
117Elfogadva638ms5516 KiB
118Elfogadva704ms6192 KiB
119Elfogadva2ms500 KiB
120Elfogadva2ms316 KiB
121Elfogadva639ms6192 KiB
122Elfogadva639ms6260 KiB
123Elfogadva680ms6112 KiB
124Elfogadva639ms5688 KiB
125Elfogadva708ms6264 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz656ms6140 KiB
129Hibás válasz656ms6156 KiB
130Hibás válasz698ms6116 KiB
131Hibás válasz654ms5684 KiB
132Elfogadva708ms6196 KiB
133Elfogadva709ms6240 KiB
134Hibás válasz716ms6196 KiB
135Hibás válasz717ms6092 KiB
136Hibás válasz723ms6212 KiB