244572026-02-11 20:44:31ubormaciMaximális összegű útcpp17Time limit exceeded 29/1002.599s9496 KiB
#include <iostream>
#include <algorithm> // for sort, mainly
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint> // for int64_t, int32_t, etc
#include <queue>
#include <stack>
#include <deque>
#include <numeric> // gcd, lcm
#include <fstream>
#include <bitset> // for bitset
#include <iomanip>
#include <cassert> // for set with custom ordering
#include <type_traits> // for set with custom ordering
#include <utility> // for swap, forward, etc
using namespace std;

#pragma GCC optimize("O2")
// #pragma GCC optimize("O1","O2","O3","Ofast","unroll-loops")
// #pragma GCC target("sse","sse2","sse3","sse4.1","sse4.2","avx","avx2","fma")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*

notes:

int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string

vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));

{if statement} ? {truth value} : {false value}

#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

std::lcm(ll a, ll b), std::gcd(int a, int b)

cout << fixed << setprecision(n);

set with custom ordering
set<ll, decltype(&cmp)> qu(cmp);

*/

typedef int64_t ll;

ll inf = INT64_MAX;
ll neginf = -inf;

bool ins(ll i, ll j, ll si, ll sj, ll n, ll m) {

	if(i < si || i >= n || j < sj || j >= m) {
		return false;
	}
	return true;

}

ll calc(ll si, ll sj, ll n, ll m, vector<vector<ll>>& v, vector<vector<ll>>& c, vector<vector<ll>>& cx) {

	//cerr << "\nsi=" << si << "; sj=" << sj;
	//cerr << "\nborders=" << cx[c[si][sj]];

	ll ret = v[si][sj];

	vector<vector<ll>> dp(n, vector<ll>(m, 0));

	for(ll i = si; i <= cx[c[si][sj]][1]; i++) {
		for(ll j = sj; j <= cx[c[si][sj]][3]; j++) {
			
			dp[i][j] = v[i][j];

			if(i == si && j == sj) {
				continue;
			}

			ll come = neginf;

			if(ins(i-1, j, si, sj, n, m)) {
				come = max(come, dp[i-1][j]);
			}
			if(ins(i, j-1, si, sj, n, m)) {
				come = max(come, dp[i][j-1]);
			}

			dp[i][j] += come;

			if(c[i][j] == c[si][sj]) {
				ret = max(ret, dp[i][j]);
			}

		}
	}

	return ret;

}

void solve() {

	ll n, m;
	cin >> n >> m;

	vector<vector<ll>> v(n, vector<ll>(m, 0));
	vector<vector<ll>> c(n, vector<ll>(m, 0));

	vector<vector<ll>> cx(501, vector<ll>(4, -1));
	// 0-min i, 1=max i, 2=min j 3 = max j

	for(ll i = 0; i < n; i++) {
		for(ll j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}

	for(ll i = 0; i < n; i++) {
		for(ll j = 0; j < m; j++) {

			cin >> c[i][j];
			
			ll ch = c[i][j];

			for(ll k = 0; k < 4; k++) {
				if(cx[ch][k] == -1) {
					if(k < 2) {
						cx[ch][k] = i;
					}else{
						cx[ch][k] = j;
					}
				}
			}

			//cerr << "\ni=" << i << "; j=" << j << "; colors=" << c[i][j];

			cx[ch][0] = min(cx[ch][0], i);
			cx[ch][1] = max(cx[ch][1], i);
			cx[ch][2] = min(cx[ch][2], j);
			cx[ch][3] = max(cx[ch][3], j);
		}
	}

	ll ans = neginf/2;

	for(ll i = 0; i < n; i++) {
		for(ll j = 0; j < m; j++) {
			ans = max(ans, calc(i, j, n, m, v, c, cx));
		}
	}

	cout << ans;

}

int main()
{
	std::ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);

	solve();

	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms508 KiB
subtask24/4
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask37/7
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted4ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted4ms316 KiB
19Accepted1ms560 KiB
20Accepted1ms316 KiB
21Accepted3ms492 KiB
22Accepted3ms508 KiB
23Accepted3ms316 KiB
24Accepted4ms316 KiB
25Accepted6ms488 KiB
26Accepted4ms316 KiB
27Accepted3ms316 KiB
subtask418/18
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted4ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted4ms316 KiB
39Accepted1ms560 KiB
40Accepted1ms316 KiB
41Accepted3ms492 KiB
42Accepted3ms508 KiB
43Accepted3ms316 KiB
44Accepted4ms316 KiB
45Accepted6ms488 KiB
46Accepted4ms316 KiB
47Accepted3ms316 KiB
48Accepted233ms628 KiB
49Accepted232ms580 KiB
50Accepted352ms744 KiB
51Accepted351ms624 KiB
52Accepted254ms564 KiB
53Accepted254ms564 KiB
54Accepted190ms764 KiB
55Accepted190ms680 KiB
56Accepted164ms784 KiB
57Accepted172ms564 KiB
58Accepted233ms796 KiB
59Accepted386ms732 KiB
60Accepted256ms564 KiB
61Accepted192ms788 KiB
subtask50/5
62Accepted2ms508 KiB
63Accepted2ms316 KiB
64Time limit exceeded2.579s7316 KiB
65Time limit exceeded2.578s7640 KiB
66Time limit exceeded2.598s8632 KiB
67Time limit exceeded2.598s8188 KiB
68Time limit exceeded2.585s8888 KiB
subtask60/12
69Accepted1ms316 KiB
70Accepted1ms508 KiB
71Time limit exceeded2.575s7236 KiB
72Time limit exceeded2.575s7304 KiB
73Time limit exceeded2.598s8736 KiB
74Time limit exceeded2.598s8012 KiB
75Time limit exceeded2.578s9240 KiB
subtask70/54
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted4ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted4ms316 KiB
89Accepted1ms560 KiB
90Accepted1ms316 KiB
91Accepted3ms492 KiB
92Accepted3ms508 KiB
93Accepted3ms316 KiB
94Accepted4ms316 KiB
95Accepted6ms488 KiB
96Accepted4ms316 KiB
97Accepted3ms316 KiB
98Accepted233ms628 KiB
99Accepted232ms580 KiB
100Accepted352ms744 KiB
101Accepted351ms624 KiB
102Accepted254ms564 KiB
103Accepted254ms564 KiB
104Accepted190ms764 KiB
105Accepted190ms680 KiB
106Accepted164ms784 KiB
107Accepted172ms564 KiB
108Accepted233ms796 KiB
109Accepted386ms732 KiB
110Accepted256ms564 KiB
111Accepted192ms788 KiB
112Accepted2ms508 KiB
113Accepted2ms316 KiB
114Time limit exceeded2.579s7316 KiB
115Time limit exceeded2.578s7640 KiB
116Time limit exceeded2.598s8632 KiB
117Time limit exceeded2.598s8188 KiB
118Time limit exceeded2.585s8888 KiB
119Accepted1ms316 KiB
120Accepted1ms508 KiB
121Time limit exceeded2.575s7236 KiB
122Time limit exceeded2.575s7304 KiB
123Time limit exceeded2.598s8736 KiB
124Time limit exceeded2.598s8012 KiB
125Time limit exceeded2.578s9240 KiB
126Accepted1ms508 KiB
127Accepted2ms316 KiB
128Time limit exceeded2.599s7872 KiB
129Time limit exceeded2.598s7780 KiB
130Time limit exceeded2.596s9072 KiB
131Time limit exceeded2.598s8796 KiB
132Time limit exceeded2.578s9076 KiB
133Time limit exceeded2.575s9032 KiB
134Time limit exceeded2.575s9184 KiB
135Time limit exceeded2.575s9196 KiB
136Time limit exceeded2.588s9496 KiB