250072026-02-17 12:14:38Leventusz09Maximális összegű útcpp17Hibás válasz 4/100722ms9644 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 || c == C[i][j]){
                        LN[c] += A[i][j];
                    }else{
                        LN[c] = 0;
                    }

                    LR[j][c] = LN[c];
                }
                else if(j==0){
                    if(LR[0][c] > 0 || c == C[i][j]){
                        LN[c] = LR[0][c] + A[i][j];
                    }else{
                        LN[c] = 0;
                    }
                }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];
            }
        }
    }
    
    
    
    /*// bal felső sarok
    int LL[M][500];
    int LN[500];
    int o=A[0][0];


    IC LC[0][c] = 0;
    IC LL[0][c] = 0;
    LN[C[0][0]] = A[0][0];

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

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

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

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

            LC[i][c] = LN[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
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Hibás válasz4ms316 KiB
16Elfogadva1ms508 KiB
17Elfogadva1ms508 KiB
18Hibás válasz3ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz3ms316 KiB
22Hibás válasz3ms316 KiB
23Hibás válasz3ms316 KiB
24Hibás válasz4ms528 KiB
25Hibás válasz3ms316 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
34Elfogadva1ms316 KiB
35Hibás válasz4ms316 KiB
36Elfogadva1ms508 KiB
37Elfogadva1ms508 KiB
38Hibás válasz3ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz3ms316 KiB
42Hibás válasz3ms316 KiB
43Hibás válasz3ms316 KiB
44Hibás válasz4ms528 KiB
45Hibás válasz3ms316 KiB
46Hibás válasz4ms316 KiB
47Hibás válasz4ms316 KiB
48Hibás válasz27ms1016 KiB
49Hibás válasz27ms944 KiB
50Hibás válasz27ms1064 KiB
51Hibás válasz27ms820 KiB
52Hibás válasz27ms908 KiB
53Hibás válasz27ms1012 KiB
54Hibás válasz28ms1012 KiB
55Hibás válasz28ms820 KiB
56Hibás válasz28ms820 KiB
57Hibás válasz28ms820 KiB
58Hibás válasz28ms1016 KiB
59Hibás válasz28ms820 KiB
60Hibás válasz28ms836 KiB
61Hibás válasz29ms1080 KiB
subtask50/5
62Elfogadva2ms548 KiB
63Elfogadva2ms560 KiB
64Elfogadva638ms7224 KiB
65Hibás válasz638ms7220 KiB
66Hibás válasz675ms9032 KiB
67Elfogadva633ms7612 KiB
68Hibás válasz703ms9268 KiB
subtask60/12
69Elfogadva2ms316 KiB
70Elfogadva2ms316 KiB
71Elfogadva638ms7368 KiB
72Hibás válasz640ms7188 KiB
73Hibás válasz683ms8876 KiB
74Elfogadva635ms8240 KiB
75Elfogadva703ms9268 KiB
subtask70/54
76Elfogadva2ms316 KiB
77Elfogadva2ms508 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms316 KiB
85Hibás válasz4ms316 KiB
86Elfogadva1ms508 KiB
87Elfogadva1ms508 KiB
88Hibás válasz3ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Hibás válasz3ms316 KiB
92Hibás válasz3ms316 KiB
93Hibás válasz3ms316 KiB
94Hibás válasz4ms528 KiB
95Hibás válasz3ms316 KiB
96Hibás válasz4ms316 KiB
97Hibás válasz4ms316 KiB
98Hibás válasz27ms1016 KiB
99Hibás válasz27ms944 KiB
100Hibás válasz27ms1064 KiB
101Hibás válasz27ms820 KiB
102Hibás válasz27ms908 KiB
103Hibás válasz27ms1012 KiB
104Hibás válasz28ms1012 KiB
105Hibás válasz28ms820 KiB
106Hibás válasz28ms820 KiB
107Hibás válasz28ms820 KiB
108Hibás válasz28ms1016 KiB
109Hibás válasz28ms820 KiB
110Hibás válasz28ms836 KiB
111Hibás válasz29ms1080 KiB
112Elfogadva2ms548 KiB
113Elfogadva2ms560 KiB
114Elfogadva638ms7224 KiB
115Hibás válasz638ms7220 KiB
116Hibás válasz675ms9032 KiB
117Elfogadva633ms7612 KiB
118Hibás válasz703ms9268 KiB
119Elfogadva2ms316 KiB
120Elfogadva2ms316 KiB
121Elfogadva638ms7368 KiB
122Hibás válasz640ms7188 KiB
123Hibás válasz683ms8876 KiB
124Elfogadva635ms8240 KiB
125Elfogadva703ms9268 KiB
126Hibás válasz2ms316 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz657ms7668 KiB
129Hibás válasz653ms7648 KiB
130Hibás válasz693ms9292 KiB
131Hibás válasz652ms8592 KiB
132Elfogadva705ms9268 KiB
133Elfogadva707ms9076 KiB
134Hibás válasz716ms8244 KiB
135Hibás válasz712ms9468 KiB
136Hibás válasz722ms9644 KiB