244572026-02-11 20:44:31ubormaciMaximális összegű útcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms508 KiB
subtask24/4
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask37/7
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva4ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva4ms316 KiB
19Elfogadva1ms560 KiB
20Elfogadva1ms316 KiB
21Elfogadva3ms492 KiB
22Elfogadva3ms508 KiB
23Elfogadva3ms316 KiB
24Elfogadva4ms316 KiB
25Elfogadva6ms488 KiB
26Elfogadva4ms316 KiB
27Elfogadva3ms316 KiB
subtask418/18
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva4ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva4ms316 KiB
39Elfogadva1ms560 KiB
40Elfogadva1ms316 KiB
41Elfogadva3ms492 KiB
42Elfogadva3ms508 KiB
43Elfogadva3ms316 KiB
44Elfogadva4ms316 KiB
45Elfogadva6ms488 KiB
46Elfogadva4ms316 KiB
47Elfogadva3ms316 KiB
48Elfogadva233ms628 KiB
49Elfogadva232ms580 KiB
50Elfogadva352ms744 KiB
51Elfogadva351ms624 KiB
52Elfogadva254ms564 KiB
53Elfogadva254ms564 KiB
54Elfogadva190ms764 KiB
55Elfogadva190ms680 KiB
56Elfogadva164ms784 KiB
57Elfogadva172ms564 KiB
58Elfogadva233ms796 KiB
59Elfogadva386ms732 KiB
60Elfogadva256ms564 KiB
61Elfogadva192ms788 KiB
subtask50/5
62Elfogadva2ms508 KiB
63Elfogadva2ms316 KiB
64Időlimit túllépés2.579s7316 KiB
65Időlimit túllépés2.578s7640 KiB
66Időlimit túllépés2.598s8632 KiB
67Időlimit túllépés2.598s8188 KiB
68Időlimit túllépés2.585s8888 KiB
subtask60/12
69Elfogadva1ms316 KiB
70Elfogadva1ms508 KiB
71Időlimit túllépés2.575s7236 KiB
72Időlimit túllépés2.575s7304 KiB
73Időlimit túllépés2.598s8736 KiB
74Időlimit túllépés2.598s8012 KiB
75Időlimit túllépés2.578s9240 KiB
subtask70/54
76Elfogadva1ms316 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms316 KiB
85Elfogadva4ms316 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva4ms316 KiB
89Elfogadva1ms560 KiB
90Elfogadva1ms316 KiB
91Elfogadva3ms492 KiB
92Elfogadva3ms508 KiB
93Elfogadva3ms316 KiB
94Elfogadva4ms316 KiB
95Elfogadva6ms488 KiB
96Elfogadva4ms316 KiB
97Elfogadva3ms316 KiB
98Elfogadva233ms628 KiB
99Elfogadva232ms580 KiB
100Elfogadva352ms744 KiB
101Elfogadva351ms624 KiB
102Elfogadva254ms564 KiB
103Elfogadva254ms564 KiB
104Elfogadva190ms764 KiB
105Elfogadva190ms680 KiB
106Elfogadva164ms784 KiB
107Elfogadva172ms564 KiB
108Elfogadva233ms796 KiB
109Elfogadva386ms732 KiB
110Elfogadva256ms564 KiB
111Elfogadva192ms788 KiB
112Elfogadva2ms508 KiB
113Elfogadva2ms316 KiB
114Időlimit túllépés2.579s7316 KiB
115Időlimit túllépés2.578s7640 KiB
116Időlimit túllépés2.598s8632 KiB
117Időlimit túllépés2.598s8188 KiB
118Időlimit túllépés2.585s8888 KiB
119Elfogadva1ms316 KiB
120Elfogadva1ms508 KiB
121Időlimit túllépés2.575s7236 KiB
122Időlimit túllépés2.575s7304 KiB
123Időlimit túllépés2.598s8736 KiB
124Időlimit túllépés2.598s8012 KiB
125Időlimit túllépés2.578s9240 KiB
126Elfogadva1ms508 KiB
127Elfogadva2ms316 KiB
128Időlimit túllépés2.599s7872 KiB
129Időlimit túllépés2.598s7780 KiB
130Időlimit túllépés2.596s9072 KiB
131Időlimit túllépés2.598s8796 KiB
132Időlimit túllépés2.578s9076 KiB
133Időlimit túllépés2.575s9032 KiB
134Időlimit túllépés2.575s9184 KiB
135Időlimit túllépés2.575s9196 KiB
136Időlimit túllépés2.588s9496 KiB