249932026-02-17 11:31:19Leventusz09Maximális összegű útcpp17Hibás válasz 4/100451ms262144 KiB
#include <iostream>
#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];

    // bal felső sarok
    IC L[0][0][c] = 0;
    L[0][0][C[0][0]] = A[0][0];

    // első sor
    for(int i=1; i<M; i++){
        IC{
            if(L[0][i-1][c] > 0 || C[0][i] == c){
                L[0][i][c] = L[0][i-1][c] + A[0][i];
            }else{
                L[0][i][c] = 0;
            }

            if(C[0][i] == c) if(L[0][i][c] > o) o = L[0][i][c];
        }
    }
    
    //első oszlop
    for(int i=1; i<N; i++){
        IC{
            if(L[i-1][0][c] > 0 || C[i][0] == c){
                L[i][0][c] = L[i-1][0][c] + A[i][0];
            }else{
                L[i][0][c] = 0;
            }

            if(C[i][0] == c) if(L[i][0][c] > o) o = L[i][0][c];
        }
    }

    // az összes többi
    for(int i=1; i<N; i++){
        for(int j=1; j<M; j++){
            IC{
                int cu = L[i-1][j][c];
                int cl = L[i][j-1][c];
                if(cu < 0 && cl < 0){
                    if(C[i][j] == c) L[i][j][c] = A[i][j];
                    else L[i][j][c] = max(cu, cl) + A[i][j];
                }
                else L[i][j][c] = max(cu, cl) + A[i][j];

                if(C[i][j] == c) if(L[i][j][c] > o) o = L[i][j][c];
            }
        }
    }
    #if DEBUG
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            IC{
                cout << L[i][j][c] << ".";
            }
            cout << "\t";
        }
        cout << "\n";
    }

    #endif
    cout << o << endl;
    
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms508 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms580 KiB
15Elfogadva4ms3724 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms564 KiB
18Elfogadva4ms3892 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz2ms748 KiB
21Hibás válasz4ms3788 KiB
22Hibás válasz4ms3124 KiB
23Hibás válasz4ms3416 KiB
24Hibás válasz6ms3724 KiB
25Elfogadva4ms3892 KiB
26Hibás válasz4ms3892 KiB
27Hibás válasz4ms3876 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms508 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms580 KiB
35Elfogadva4ms3724 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms564 KiB
38Elfogadva4ms3892 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz2ms748 KiB
41Hibás válasz4ms3788 KiB
42Hibás válasz4ms3124 KiB
43Hibás válasz4ms3416 KiB
44Hibás válasz6ms3724 KiB
45Elfogadva4ms3892 KiB
46Hibás válasz4ms3892 KiB
47Hibás válasz4ms3876 KiB
48Hibás válasz48ms39476 KiB
49Elfogadva41ms39580 KiB
50Elfogadva41ms39452 KiB
51Elfogadva48ms39564 KiB
52Hibás válasz48ms39476 KiB
53Hibás válasz48ms39476 KiB
54Hibás válasz41ms39660 KiB
55Hibás válasz41ms39620 KiB
56Hibás válasz48ms36916 KiB
57Hibás válasz50ms37172 KiB
58Hibás válasz43ms39476 KiB
59Hibás válasz50ms39476 KiB
60Hibás válasz48ms39580 KiB
61Hibás válasz43ms39516 KiB
subtask50/5
62Elfogadva2ms316 KiB
63Elfogadva2ms564 KiB
64Futási hiba381ms262144 KiB
65Futási hiba335ms262144 KiB
66Futási hiba398ms262144 KiB
67Futási hiba435ms262144 KiB
68Futási hiba402ms262144 KiB
subtask60/12
69Elfogadva2ms316 KiB
70Elfogadva2ms568 KiB
71Futási hiba333ms262144 KiB
72Futási hiba333ms262144 KiB
73Futási hiba435ms262144 KiB
74Futási hiba428ms262144 KiB
75Futási hiba393ms262144 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms508 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms580 KiB
85Elfogadva4ms3724 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms564 KiB
88Elfogadva4ms3892 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz2ms748 KiB
91Hibás válasz4ms3788 KiB
92Hibás válasz4ms3124 KiB
93Hibás válasz4ms3416 KiB
94Hibás válasz6ms3724 KiB
95Elfogadva4ms3892 KiB
96Hibás válasz4ms3892 KiB
97Hibás válasz4ms3876 KiB
98Hibás válasz48ms39476 KiB
99Elfogadva41ms39580 KiB
100Elfogadva41ms39452 KiB
101Elfogadva48ms39564 KiB
102Hibás válasz48ms39476 KiB
103Hibás válasz48ms39476 KiB
104Hibás válasz41ms39660 KiB
105Hibás válasz41ms39620 KiB
106Hibás válasz48ms36916 KiB
107Hibás válasz50ms37172 KiB
108Hibás válasz43ms39476 KiB
109Hibás válasz50ms39476 KiB
110Hibás válasz48ms39580 KiB
111Hibás válasz43ms39516 KiB
112Elfogadva2ms316 KiB
113Elfogadva2ms564 KiB
114Futási hiba381ms262144 KiB
115Futási hiba335ms262144 KiB
116Futási hiba398ms262144 KiB
117Futási hiba435ms262144 KiB
118Futási hiba402ms262144 KiB
119Elfogadva2ms316 KiB
120Elfogadva2ms568 KiB
121Futási hiba333ms262144 KiB
122Futási hiba333ms262144 KiB
123Futási hiba435ms262144 KiB
124Futási hiba428ms262144 KiB
125Futási hiba393ms262144 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz2ms564 KiB
128Futási hiba398ms262144 KiB
129Futási hiba395ms262144 KiB
130Futási hiba407ms262144 KiB
131Futási hiba395ms262144 KiB
132Futási hiba444ms262144 KiB
133Futási hiba444ms262144 KiB
134Futási hiba451ms262144 KiB
135Futási hiba402ms262144 KiB
136Futási hiba407ms262144 KiB