| 24457 | 2026-02-11 20:44:31 | ubormaci | Maximális összegű út | cpp17 | Időlimit túllépés 29/100 | 2.599s | 9496 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 1ms | 508 KiB | ||||
| subtask2 | 4/4 | ||||||
| 3 | Elfogadva | 1ms | 316 KiB | ||||
| 4 | Elfogadva | 1ms | 316 KiB | ||||
| 5 | Elfogadva | 1ms | 316 KiB | ||||
| 6 | Elfogadva | 1ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 7/7 | ||||||
| 8 | Elfogadva | 1ms | 316 KiB | ||||
| 9 | Elfogadva | 1ms | 316 KiB | ||||
| 10 | Elfogadva | 1ms | 316 KiB | ||||
| 11 | Elfogadva | 1ms | 316 KiB | ||||
| 12 | Elfogadva | 1ms | 316 KiB | ||||
| 13 | Elfogadva | 1ms | 316 KiB | ||||
| 14 | Elfogadva | 1ms | 316 KiB | ||||
| 15 | Elfogadva | 4ms | 316 KiB | ||||
| 16 | Elfogadva | 1ms | 316 KiB | ||||
| 17 | Elfogadva | 1ms | 316 KiB | ||||
| 18 | Elfogadva | 4ms | 316 KiB | ||||
| 19 | Elfogadva | 1ms | 560 KiB | ||||
| 20 | Elfogadva | 1ms | 316 KiB | ||||
| 21 | Elfogadva | 3ms | 492 KiB | ||||
| 22 | Elfogadva | 3ms | 508 KiB | ||||
| 23 | Elfogadva | 3ms | 316 KiB | ||||
| 24 | Elfogadva | 4ms | 316 KiB | ||||
| 25 | Elfogadva | 6ms | 488 KiB | ||||
| 26 | Elfogadva | 4ms | 316 KiB | ||||
| 27 | Elfogadva | 3ms | 316 KiB | ||||
| subtask4 | 18/18 | ||||||
| 28 | Elfogadva | 1ms | 316 KiB | ||||
| 29 | Elfogadva | 1ms | 316 KiB | ||||
| 30 | Elfogadva | 1ms | 316 KiB | ||||
| 31 | Elfogadva | 1ms | 316 KiB | ||||
| 32 | Elfogadva | 1ms | 316 KiB | ||||
| 33 | Elfogadva | 1ms | 316 KiB | ||||
| 34 | Elfogadva | 1ms | 316 KiB | ||||
| 35 | Elfogadva | 4ms | 316 KiB | ||||
| 36 | Elfogadva | 1ms | 316 KiB | ||||
| 37 | Elfogadva | 1ms | 316 KiB | ||||
| 38 | Elfogadva | 4ms | 316 KiB | ||||
| 39 | Elfogadva | 1ms | 560 KiB | ||||
| 40 | Elfogadva | 1ms | 316 KiB | ||||
| 41 | Elfogadva | 3ms | 492 KiB | ||||
| 42 | Elfogadva | 3ms | 508 KiB | ||||
| 43 | Elfogadva | 3ms | 316 KiB | ||||
| 44 | Elfogadva | 4ms | 316 KiB | ||||
| 45 | Elfogadva | 6ms | 488 KiB | ||||
| 46 | Elfogadva | 4ms | 316 KiB | ||||
| 47 | Elfogadva | 3ms | 316 KiB | ||||
| 48 | Elfogadva | 233ms | 628 KiB | ||||
| 49 | Elfogadva | 232ms | 580 KiB | ||||
| 50 | Elfogadva | 352ms | 744 KiB | ||||
| 51 | Elfogadva | 351ms | 624 KiB | ||||
| 52 | Elfogadva | 254ms | 564 KiB | ||||
| 53 | Elfogadva | 254ms | 564 KiB | ||||
| 54 | Elfogadva | 190ms | 764 KiB | ||||
| 55 | Elfogadva | 190ms | 680 KiB | ||||
| 56 | Elfogadva | 164ms | 784 KiB | ||||
| 57 | Elfogadva | 172ms | 564 KiB | ||||
| 58 | Elfogadva | 233ms | 796 KiB | ||||
| 59 | Elfogadva | 386ms | 732 KiB | ||||
| 60 | Elfogadva | 256ms | 564 KiB | ||||
| 61 | Elfogadva | 192ms | 788 KiB | ||||
| subtask5 | 0/5 | ||||||
| 62 | Elfogadva | 2ms | 508 KiB | ||||
| 63 | Elfogadva | 2ms | 316 KiB | ||||
| 64 | Időlimit túllépés | 2.579s | 7316 KiB | ||||
| 65 | Időlimit túllépés | 2.578s | 7640 KiB | ||||
| 66 | Időlimit túllépés | 2.598s | 8632 KiB | ||||
| 67 | Időlimit túllépés | 2.598s | 8188 KiB | ||||
| 68 | Időlimit túllépés | 2.585s | 8888 KiB | ||||
| subtask6 | 0/12 | ||||||
| 69 | Elfogadva | 1ms | 316 KiB | ||||
| 70 | Elfogadva | 1ms | 508 KiB | ||||
| 71 | Időlimit túllépés | 2.575s | 7236 KiB | ||||
| 72 | Időlimit túllépés | 2.575s | 7304 KiB | ||||
| 73 | Időlimit túllépés | 2.598s | 8736 KiB | ||||
| 74 | Időlimit túllépés | 2.598s | 8012 KiB | ||||
| 75 | Időlimit túllépés | 2.578s | 9240 KiB | ||||
| subtask7 | 0/54 | ||||||
| 76 | Elfogadva | 1ms | 316 KiB | ||||
| 77 | Elfogadva | 1ms | 316 KiB | ||||
| 78 | Elfogadva | 1ms | 316 KiB | ||||
| 79 | Elfogadva | 1ms | 316 KiB | ||||
| 80 | Elfogadva | 1ms | 316 KiB | ||||
| 81 | Elfogadva | 1ms | 316 KiB | ||||
| 82 | Elfogadva | 1ms | 316 KiB | ||||
| 83 | Elfogadva | 1ms | 316 KiB | ||||
| 84 | Elfogadva | 1ms | 316 KiB | ||||
| 85 | Elfogadva | 4ms | 316 KiB | ||||
| 86 | Elfogadva | 1ms | 316 KiB | ||||
| 87 | Elfogadva | 1ms | 316 KiB | ||||
| 88 | Elfogadva | 4ms | 316 KiB | ||||
| 89 | Elfogadva | 1ms | 560 KiB | ||||
| 90 | Elfogadva | 1ms | 316 KiB | ||||
| 91 | Elfogadva | 3ms | 492 KiB | ||||
| 92 | Elfogadva | 3ms | 508 KiB | ||||
| 93 | Elfogadva | 3ms | 316 KiB | ||||
| 94 | Elfogadva | 4ms | 316 KiB | ||||
| 95 | Elfogadva | 6ms | 488 KiB | ||||
| 96 | Elfogadva | 4ms | 316 KiB | ||||
| 97 | Elfogadva | 3ms | 316 KiB | ||||
| 98 | Elfogadva | 233ms | 628 KiB | ||||
| 99 | Elfogadva | 232ms | 580 KiB | ||||
| 100 | Elfogadva | 352ms | 744 KiB | ||||
| 101 | Elfogadva | 351ms | 624 KiB | ||||
| 102 | Elfogadva | 254ms | 564 KiB | ||||
| 103 | Elfogadva | 254ms | 564 KiB | ||||
| 104 | Elfogadva | 190ms | 764 KiB | ||||
| 105 | Elfogadva | 190ms | 680 KiB | ||||
| 106 | Elfogadva | 164ms | 784 KiB | ||||
| 107 | Elfogadva | 172ms | 564 KiB | ||||
| 108 | Elfogadva | 233ms | 796 KiB | ||||
| 109 | Elfogadva | 386ms | 732 KiB | ||||
| 110 | Elfogadva | 256ms | 564 KiB | ||||
| 111 | Elfogadva | 192ms | 788 KiB | ||||
| 112 | Elfogadva | 2ms | 508 KiB | ||||
| 113 | Elfogadva | 2ms | 316 KiB | ||||
| 114 | Időlimit túllépés | 2.579s | 7316 KiB | ||||
| 115 | Időlimit túllépés | 2.578s | 7640 KiB | ||||
| 116 | Időlimit túllépés | 2.598s | 8632 KiB | ||||
| 117 | Időlimit túllépés | 2.598s | 8188 KiB | ||||
| 118 | Időlimit túllépés | 2.585s | 8888 KiB | ||||
| 119 | Elfogadva | 1ms | 316 KiB | ||||
| 120 | Elfogadva | 1ms | 508 KiB | ||||
| 121 | Időlimit túllépés | 2.575s | 7236 KiB | ||||
| 122 | Időlimit túllépés | 2.575s | 7304 KiB | ||||
| 123 | Időlimit túllépés | 2.598s | 8736 KiB | ||||
| 124 | Időlimit túllépés | 2.598s | 8012 KiB | ||||
| 125 | Időlimit túllépés | 2.578s | 9240 KiB | ||||
| 126 | Elfogadva | 1ms | 508 KiB | ||||
| 127 | Elfogadva | 2ms | 316 KiB | ||||
| 128 | Időlimit túllépés | 2.599s | 7872 KiB | ||||
| 129 | Időlimit túllépés | 2.598s | 7780 KiB | ||||
| 130 | Időlimit túllépés | 2.596s | 9072 KiB | ||||
| 131 | Időlimit túllépés | 2.598s | 8796 KiB | ||||
| 132 | Időlimit túllépés | 2.578s | 9076 KiB | ||||
| 133 | Időlimit túllépés | 2.575s | 9032 KiB | ||||
| 134 | Időlimit túllépés | 2.575s | 9184 KiB | ||||
| 135 | Időlimit túllépés | 2.575s | 9196 KiB | ||||
| 136 | Időlimit túllépés | 2.588s | 9496 KiB | ||||