Submission #1263836

#TimeUsernameProblemLanguageResultExecution timeMemory
1263836LIANafta (COI15_nafta)C++17
34 / 100
1079 ms97440 KiB
#include <bits/stdc++.h> #define ll long long const ll inf = 1e19 + 7; using namespace std; ll r, c, n; vector<string> grid; vector<pair<ll, ll>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; vector<vector<bool>> vis; vector<tuple<ll, ll, ll>> ranges; vector<vector<ll>> dp, profit; bool lol(ll i, ll j) { return (i >= 1 && j >= 1 && i <= r && j <= c && !vis[i][j] && grid[i][j - 1] != '.'); } ll lf, ri, sum = 0; void dfs(ll i, ll j) { lf = min(lf, j); ri = max(ri, j); vis[i][j] = 1; sum += (grid[i][j - 1] - '0'); for (auto [x, y] : dir) { if (lol(i + x, j + y)) dfs(i + x, j + y); } } void calc_dp() { for (ll k = 1; k <= c; ++k) { for (ll i = 1; i <= c; ++i) { ll best = 0; for (ll j = 0; j < i; ++j) { best = max(best, dp[j][k - 1] + profit[i][j]); } dp[i][k] = best; } } } void build_profit() { vector<vector<pair<ll, ll>>> byR(c + 2); for (auto &t : ranges) { ll L = get<0>(t), R = get<1>(t), W = get<2>(t); if (L < 1) L = 1; if (R > c) R = c; if (L > R) continue; byR[R].push_back({L, W}); } vector<ll> add(c + 2, 0), pref(c + 2, 0); for (ll i = c; i >= 1; --i) { for (auto &pr : byR[i]) add[pr.first] += pr.second; pref[0] = 0; for (ll x = 1; x <= c; ++x) pref[x] = pref[x - 1] + add[x]; ll total_to_i = pref[i]; for (ll j = 0; j < i; ++j) { profit[i][j] = total_to_i - pref[j]; } } } int main() { cin >> r >> c; grid.resize(r + 1); vis.resize(r + 1, vector<bool>(c + 1)); profit.resize(c + 2, vector<ll>(c + 2)); dp.resize(c + 2, vector<ll>(c + 2)); for (ll i = 1; i <= r; ++i) cin >> grid[i]; for (ll i = 1; i <= r; ++i) { for (ll j = 1; j <= c; ++j) { if (lol(i, j)) { lf = inf; ri = -1; sum = 0; dfs(i, j); ranges.push_back({lf, ri, sum}); } } } build_profit(); calc_dp(); ll pref = 0; for (ll k = 1; k <= c; k++) { ll best = 0; for (ll i = 1; i <= c; i++) best = max(best, dp[i][k]); pref = max(pref, best); cout << pref << endl; } }

Compilation message (stderr)

nafta.cpp:3:21: warning: overflow in conversion from 'double' to 'long long int' changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
    3 | const ll inf = 1e19 + 7;
      |                ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...