Submission #25,315

2026-02-19 09:27:58

cpp17

Accepted 100/100

476ms

6224 KiB

#include <limits.h>
#include <iostream>
#include <vector>
#define DEBUG false
#define int long long
#define LX LLONG_MIN

#if DEBUG
#define IC for(int c=0; c<2; c++)
#else
#define IC for(int c=0; c<500; c++)
#endif

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{
                int lu, ll;
                if(i == 0) lu = LX;
                else lu = LR[j][c];
                if(j == 0) ll = LX;
                else ll= LN[c];

                if(c == C[i][j]) LN[c] = max(0LL, max(ll, lu)) + A[i][j];
                else {
                    if(lu == LX){
                        if(ll == LX) LN[c] = LX;
                        else LN[c] = ll + A[i][j];
                    }else{
                        if(ll == LX) LN[c] = lu + A[i][j];
                        else LN[c] = max(lu, ll) + A[i][j];
                    }
                }
                LR[j][c] = LN[c];

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

        #if DEBUG
        for(int i=0; i<M; i++){
            IC{
                cout << LR[i][c] << ".";
            }
            cout << " ";
        }
        cout << endl;
        #endif
    }

    cout << o << endl;
    
    return 0;
}

/*
3 3
1 1 1
1 1 1
1 1 1
1 2 3
4 5 6
7 8 9

*/

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	1ms	500 KiB
		2	Accepted	1ms	316 KiB
subtask2	4/4
		3	Accepted	1ms	316 KiB
		4	Accepted	2ms	316 KiB
		5	Accepted	1ms	376 KiB
		6	Accepted	1ms	316 KiB
		7	Accepted	1ms	316 KiB
subtask3	7/7
		8	Accepted	1ms	316 KiB
		9	Accepted	2ms	316 KiB
		10	Accepted	1ms	376 KiB
		11	Accepted	1ms	316 KiB
		12	Accepted	1ms	316 KiB
		13	Accepted	1ms	316 KiB
		14	Accepted	1ms	316 KiB
		15	Accepted	2ms	316 KiB
		16	Accepted	1ms	508 KiB
		17	Accepted	1ms	316 KiB
		18	Accepted	2ms	316 KiB
		19	Accepted	1ms	388 KiB
		20	Accepted	1ms	316 KiB
		21	Accepted	4ms	536 KiB
		22	Accepted	3ms	540 KiB
		23	Accepted	3ms	316 KiB
		24	Accepted	3ms	316 KiB
		25	Accepted	3ms	316 KiB
		26	Accepted	3ms	316 KiB
		27	Accepted	4ms	508 KiB
subtask4	18/18
		28	Accepted	1ms	316 KiB
		29	Accepted	2ms	316 KiB
		30	Accepted	1ms	376 KiB
		31	Accepted	1ms	316 KiB
		32	Accepted	1ms	316 KiB
		33	Accepted	1ms	316 KiB
		34	Accepted	1ms	316 KiB
		35	Accepted	2ms	316 KiB
		36	Accepted	1ms	508 KiB
		37	Accepted	1ms	316 KiB
		38	Accepted	2ms	316 KiB
		39	Accepted	1ms	388 KiB
		40	Accepted	1ms	316 KiB
		41	Accepted	4ms	536 KiB
		42	Accepted	3ms	540 KiB
		43	Accepted	3ms	316 KiB
		44	Accepted	3ms	316 KiB
		45	Accepted	3ms	316 KiB
		46	Accepted	3ms	316 KiB
		47	Accepted	4ms	508 KiB
		48	Accepted	17ms	804 KiB
		49	Accepted	17ms	820 KiB
		50	Accepted	17ms	916 KiB
		51	Accepted	17ms	944 KiB
		52	Accepted	17ms	820 KiB
		53	Accepted	17ms	1124 KiB
		54	Accepted	21ms	820 KiB
		55	Accepted	21ms	820 KiB
		56	Accepted	23ms	820 KiB
		57	Accepted	23ms	820 KiB
		58	Accepted	20ms	948 KiB
		59	Accepted	19ms	820 KiB
		60	Accepted	20ms	1012 KiB
		61	Accepted	25ms	1160 KiB
subtask5	5/5
		62	Accepted	2ms	316 KiB
		63	Accepted	2ms	316 KiB
		64	Accepted	402ms	6188 KiB
		65	Accepted	402ms	6196 KiB
		66	Accepted	449ms	5940 KiB
		67	Accepted	423ms	5684 KiB
		68	Accepted	467ms	6196 KiB
subtask6	12/12
		69	Accepted	1ms	508 KiB
		70	Accepted	2ms	508 KiB
		71	Accepted	404ms	6196 KiB
		72	Accepted	404ms	6120 KiB
		73	Accepted	451ms	5936 KiB
		74	Accepted	423ms	5636 KiB
		75	Accepted	469ms	6196 KiB
subtask7	54/54
		76	Accepted	2ms	316 KiB
		77	Accepted	1ms	316 KiB
		78	Accepted	1ms	316 KiB
		79	Accepted	2ms	316 KiB
		80	Accepted	1ms	376 KiB
		81	Accepted	1ms	316 KiB
		82	Accepted	1ms	316 KiB
		83	Accepted	1ms	316 KiB
		84	Accepted	1ms	316 KiB
		85	Accepted	2ms	316 KiB
		86	Accepted	1ms	508 KiB
		87	Accepted	1ms	316 KiB
		88	Accepted	2ms	316 KiB
		89	Accepted	1ms	388 KiB
		90	Accepted	1ms	316 KiB
		91	Accepted	4ms	536 KiB
		92	Accepted	3ms	540 KiB
		93	Accepted	3ms	316 KiB
		94	Accepted	3ms	316 KiB
		95	Accepted	3ms	316 KiB
		96	Accepted	3ms	316 KiB
		97	Accepted	4ms	508 KiB
		98	Accepted	17ms	804 KiB
		99	Accepted	17ms	820 KiB
		100	Accepted	17ms	916 KiB
		101	Accepted	17ms	944 KiB
		102	Accepted	17ms	820 KiB
		103	Accepted	17ms	1124 KiB
		104	Accepted	21ms	820 KiB
		105	Accepted	21ms	820 KiB
		106	Accepted	23ms	820 KiB
		107	Accepted	23ms	820 KiB
		108	Accepted	20ms	948 KiB
		109	Accepted	19ms	820 KiB
		110	Accepted	20ms	1012 KiB
		111	Accepted	25ms	1160 KiB
		112	Accepted	2ms	316 KiB
		113	Accepted	2ms	316 KiB
		114	Accepted	402ms	6188 KiB
		115	Accepted	402ms	6196 KiB
		116	Accepted	449ms	5940 KiB
		117	Accepted	423ms	5684 KiB
		118	Accepted	467ms	6196 KiB
		119	Accepted	1ms	508 KiB
		120	Accepted	2ms	508 KiB
		121	Accepted	404ms	6196 KiB
		122	Accepted	404ms	6120 KiB
		123	Accepted	451ms	5936 KiB
		124	Accepted	423ms	5636 KiB
		125	Accepted	469ms	6196 KiB
		126	Accepted	1ms	508 KiB
		127	Accepted	1ms	316 KiB
		128	Accepted	368ms	6064 KiB
		129	Accepted	368ms	6192 KiB
		130	Accepted	418ms	6048 KiB
		131	Accepted	395ms	5688 KiB
		132	Accepted	470ms	6224 KiB
		133	Accepted	472ms	6212 KiB
		134	Accepted	476ms	6196 KiB
		135	Accepted	476ms	6084 KiB
		136	Accepted	437ms	6196 KiB