250082026-02-17 12:20:26Leventusz09Maximális összegű útcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Wrong answer1ms316 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted2ms544 KiB
14Accepted1ms316 KiB
15Wrong answer2ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms316 KiB
18Wrong answer2ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms508 KiB
21Wrong answer3ms316 KiB
22Wrong answer3ms508 KiB
23Wrong answer3ms316 KiB
24Wrong answer3ms316 KiB
25Wrong answer3ms532 KiB
26Wrong answer3ms408 KiB
27Wrong answer3ms528 KiB
subtask40/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted2ms544 KiB
34Accepted1ms316 KiB
35Wrong answer2ms316 KiB
36Accepted1ms508 KiB
37Accepted1ms316 KiB
38Wrong answer2ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms508 KiB
41Wrong answer3ms316 KiB
42Wrong answer3ms508 KiB
43Wrong answer3ms316 KiB
44Wrong answer3ms316 KiB
45Wrong answer3ms532 KiB
46Wrong answer3ms408 KiB
47Wrong answer3ms528 KiB
48Wrong answer17ms820 KiB
49Wrong answer17ms948 KiB
50Wrong answer17ms944 KiB
51Wrong answer17ms944 KiB
52Wrong answer17ms948 KiB
53Wrong answer17ms940 KiB
54Wrong answer17ms948 KiB
55Wrong answer17ms944 KiB
56Wrong answer19ms1120 KiB
57Wrong answer20ms820 KiB
58Wrong answer20ms820 KiB
59Wrong answer20ms944 KiB
60Wrong answer19ms1076 KiB
61Wrong answer20ms820 KiB
subtask50/5
62Accepted2ms500 KiB
63Accepted1ms568 KiB
64Wrong answer402ms6192 KiB
65Wrong answer404ms6240 KiB
66Wrong answer458ms5872 KiB
67Accepted430ms5700 KiB
68Wrong answer476ms6196 KiB
subtask60/12
69Accepted1ms500 KiB
70Accepted2ms316 KiB
71Accepted405ms6196 KiB
72Wrong answer405ms6196 KiB
73Wrong answer458ms5896 KiB
74Wrong answer430ms5696 KiB
75Wrong answer476ms6196 KiB
subtask70/54
76Accepted1ms508 KiB
77Wrong answer1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted2ms544 KiB
84Accepted1ms316 KiB
85Wrong answer2ms316 KiB
86Accepted1ms508 KiB
87Accepted1ms316 KiB
88Wrong answer2ms316 KiB
89Wrong answer1ms316 KiB
90Wrong answer1ms508 KiB
91Wrong answer3ms316 KiB
92Wrong answer3ms508 KiB
93Wrong answer3ms316 KiB
94Wrong answer3ms316 KiB
95Wrong answer3ms532 KiB
96Wrong answer3ms408 KiB
97Wrong answer3ms528 KiB
98Wrong answer17ms820 KiB
99Wrong answer17ms948 KiB
100Wrong answer17ms944 KiB
101Wrong answer17ms944 KiB
102Wrong answer17ms948 KiB
103Wrong answer17ms940 KiB
104Wrong answer17ms948 KiB
105Wrong answer17ms944 KiB
106Wrong answer19ms1120 KiB
107Wrong answer20ms820 KiB
108Wrong answer20ms820 KiB
109Wrong answer20ms944 KiB
110Wrong answer19ms1076 KiB
111Wrong answer20ms820 KiB
112Accepted2ms500 KiB
113Accepted1ms568 KiB
114Wrong answer402ms6192 KiB
115Wrong answer404ms6240 KiB
116Wrong answer458ms5872 KiB
117Accepted430ms5700 KiB
118Wrong answer476ms6196 KiB
119Accepted1ms500 KiB
120Accepted2ms316 KiB
121Accepted405ms6196 KiB
122Wrong answer405ms6196 KiB
123Wrong answer458ms5896 KiB
124Wrong answer430ms5696 KiB
125Wrong answer476ms6196 KiB
126Wrong answer2ms316 KiB
127Wrong answer2ms316 KiB
128Wrong answer423ms6112 KiB
129Wrong answer423ms6168 KiB
130Wrong answer474ms6112 KiB
131Wrong answer446ms5548 KiB
132Wrong answer477ms6196 KiB
133Wrong answer479ms6196 KiB
134Wrong answer488ms6196 KiB
135Wrong answer485ms6028 KiB
136Wrong answer493ms6196 KiB