250082026-02-17 12:20:26Leventusz09Maximális összegű útcpp17Hibás válasz 4/100493ms6240 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] = 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] = 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
2Hibás válasz1ms316 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
13Elfogadva2ms544 KiB
14Elfogadva1ms316 KiB
15Hibás válasz2ms316 KiB
16Elfogadva1ms508 KiB
17Elfogadva1ms316 KiB
18Hibás válasz2ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms508 KiB
21Hibás válasz3ms316 KiB
22Hibás válasz3ms508 KiB
23Hibás válasz3ms316 KiB
24Hibás válasz3ms316 KiB
25Hibás válasz3ms532 KiB
26Hibás válasz3ms408 KiB
27Hibás válasz3ms528 KiB
subtask40/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva2ms544 KiB
34Elfogadva1ms316 KiB
35Hibás válasz2ms316 KiB
36Elfogadva1ms508 KiB
37Elfogadva1ms316 KiB
38Hibás válasz2ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms508 KiB
41Hibás válasz3ms316 KiB
42Hibás válasz3ms508 KiB
43Hibás válasz3ms316 KiB
44Hibás válasz3ms316 KiB
45Hibás válasz3ms532 KiB
46Hibás válasz3ms408 KiB
47Hibás válasz3ms528 KiB
48Hibás válasz17ms820 KiB
49Hibás válasz17ms948 KiB
50Hibás válasz17ms944 KiB
51Hibás válasz17ms944 KiB
52Hibás válasz17ms948 KiB
53Hibás válasz17ms940 KiB
54Hibás válasz17ms948 KiB
55Hibás válasz17ms944 KiB
56Hibás válasz19ms1120 KiB
57Hibás válasz20ms820 KiB
58Hibás válasz20ms820 KiB
59Hibás válasz20ms944 KiB
60Hibás válasz19ms1076 KiB
61Hibás válasz20ms820 KiB
subtask50/5
62Elfogadva2ms500 KiB
63Elfogadva1ms568 KiB
64Hibás válasz402ms6192 KiB
65Hibás válasz404ms6240 KiB
66Hibás válasz458ms5872 KiB
67Elfogadva430ms5700 KiB
68Hibás válasz476ms6196 KiB
subtask60/12
69Elfogadva1ms500 KiB
70Elfogadva2ms316 KiB
71Elfogadva405ms6196 KiB
72Hibás válasz405ms6196 KiB
73Hibás válasz458ms5896 KiB
74Hibás válasz430ms5696 KiB
75Hibás válasz476ms6196 KiB
subtask70/54
76Elfogadva1ms508 KiB
77Hibás válasz1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva2ms544 KiB
84Elfogadva1ms316 KiB
85Hibás válasz2ms316 KiB
86Elfogadva1ms508 KiB
87Elfogadva1ms316 KiB
88Hibás válasz2ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms508 KiB
91Hibás válasz3ms316 KiB
92Hibás válasz3ms508 KiB
93Hibás válasz3ms316 KiB
94Hibás válasz3ms316 KiB
95Hibás válasz3ms532 KiB
96Hibás válasz3ms408 KiB
97Hibás válasz3ms528 KiB
98Hibás válasz17ms820 KiB
99Hibás válasz17ms948 KiB
100Hibás válasz17ms944 KiB
101Hibás válasz17ms944 KiB
102Hibás válasz17ms948 KiB
103Hibás válasz17ms940 KiB
104Hibás válasz17ms948 KiB
105Hibás válasz17ms944 KiB
106Hibás válasz19ms1120 KiB
107Hibás válasz20ms820 KiB
108Hibás válasz20ms820 KiB
109Hibás válasz20ms944 KiB
110Hibás válasz19ms1076 KiB
111Hibás válasz20ms820 KiB
112Elfogadva2ms500 KiB
113Elfogadva1ms568 KiB
114Hibás válasz402ms6192 KiB
115Hibás válasz404ms6240 KiB
116Hibás válasz458ms5872 KiB
117Elfogadva430ms5700 KiB
118Hibás válasz476ms6196 KiB
119Elfogadva1ms500 KiB
120Elfogadva2ms316 KiB
121Elfogadva405ms6196 KiB
122Hibás válasz405ms6196 KiB
123Hibás válasz458ms5896 KiB
124Hibás válasz430ms5696 KiB
125Hibás válasz476ms6196 KiB
126Hibás válasz2ms316 KiB
127Hibás válasz2ms316 KiB
128Hibás válasz423ms6112 KiB
129Hibás válasz423ms6168 KiB
130Hibás válasz474ms6112 KiB
131Hibás válasz446ms5548 KiB
132Hibás válasz477ms6196 KiB
133Hibás válasz479ms6196 KiB
134Hibás válasz488ms6196 KiB
135Hibás válasz485ms6028 KiB
136Hibás válasz493ms6196 KiB