Submission #1263655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263655		LIA	Nafta (COI15_nafta)	C++17	34 / 100	1099 ms	83624 KiB

nafta

#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<ll> pref;
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 proc_dp() {
  vector<vector<ll>> add(c + 2, vector<ll>(c + 2, 0));
  for (auto [L, R, W] : ranges) {
    if (L < 1)
      L = 1;
    if (R > c)
      R = c;
    if (L > R)
      continue;
    add[L][R] += W;
  }

  vector<vector<ll>> suf(c + 2, vector<ll>(c + 3, 0));
  for (ll L = 1; L <= c; ++L)
    for (ll x = c; x >= 1; --x)
      suf[L][x] = suf[L][x + 1] + add[L][x];

  vector<ll> ans(c + 1, 0);
  vector<ll> dp_prev(c + 1, 0), dp_cur(c + 1, 0);

  for (ll t = 1; t <= c; ++t) {
    fill(dp_cur.begin(), dp_cur.end(), 0);
    ll best_over_i = 0;
    for (ll i = 1; i <= c; ++i) {
      ll acc = 0, best = 0;
      for (ll k = i; k >= 1; --k) {
        acc += suf[k][i];
        best = max(best, dp_prev[k - 1] + acc);
      }
      dp_cur[i] = best;
      best_over_i = max(best_over_i, best);
    }
    ans[t] = max(ans[t - 1], best_over_i);
    dp_prev.swap(dp_cur);
  }

  for (ll k = 1; k <= c; ++k)
    cout << ans[k] << "\n";
}

int main() {
  cin >> r >> c;
  grid.resize(r + 1);
  vis.resize(r + 1, vector<bool>(c + 1));

  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});
      }
    }
  }
  proc_dp();
  vector<ll> ans(c + 1);
}

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: 23 / 23
• Subtask 3: 0 / 66