Submission #1263494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263494		LIA	Nafta (COI15_nafta)	C++17	11 / 100	1099 ms	137028 KiB

nafta

#include <bits/stdc++.h>
#define ll long long
const ll inf = 1e19 + 7;
using namespace std;

ll r, c;
vector<vector<pair<ll, vector<bool>>>> dp;
vector<string> grid;
ll idx = 0, szcnt = 0;
vector<ll> sizes;
vector<pair<ll, ll>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> vis;
vector<vector<ll>> color;

bool lol(ll i, ll j) {
  return (i >= 1 && j >= 1 && i <= r && j <= c && !vis[i][j] &&
          grid[i][j - 1] != '.');
}

void dfs(ll i, ll j) {
  color[i][j] = idx;
  vis[i][j] = 1;
  if (grid[i][j - 1] != '.')
    szcnt += (grid[i][j - 1] - '0');
  for (auto [x, y] : dir) {
    if (lol(i + x, j + y))
      dfs(i + x, j + y);
  }
}

void build_dp() {
  for (ll i = 1; i <= c; ++i) {
    for (ll j = 1; j <= c; ++j) {
      for (ll x = 1; x <= i; ++x) {
        const auto &prev = dp[x][j - 1];
        ll val = prev.first;
        const auto &vec = prev.second;

        ll add = 0;
        vector<bool> visit = vec;
        for (ll row = 1; row <= r; ++row) {
          if (grid[row][i - 1] == '.')
            continue;
          ll comp = color[row][i];
          if (!visit[comp] && grid[row][i - 1] != '.') {
            visit[comp] = 1;
            add += sizes[comp];
          }
        }
        if (val + add > dp[i][j].first)
          dp[i][j] = {val + add, std::move(visit)};
      }
    }
  }
}

int main() {
  cin >> r >> c;
  grid.resize(r + 1);
  vis.resize(r + 1, vector<bool>(c + 1));
  color.resize(r + 1, vector<ll>(c + 1));
  sizes.resize(r * 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 (!vis[i][j] && grid[i][j - 1] != '.') {
        dfs(i, j);
        sizes[idx] = szcnt;
        szcnt = 0;
        idx++;
      }
    }
  }

  dp.assign(c + 1,
            vector<pair<ll, vector<bool>>>(c + 1, {0, vector<bool>(idx + 1)}));
  build_dp();

  vector<ll> ans(c + 1);

  for (ll j = 1, pref = 0; j <= c; ++j) {
    ll best = 0;
    for (ll i = 1; i <= c; ++i)
      best = max(best, dp[i][j].first);
    pref = max(pref, best);
    cout << pref << "\n"; 
  }
}

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;
      |                ~~~~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66