Submission #1263842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263842		LIA	Nafta (COI15_nafta)	C++17	100 / 100	363 ms	118436 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<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 dc(ll l, ll r, ll optl, ll optr, ll k) {
  if (l > r)
    return;
  ll mid = (l + r) >> 1;

  pair<ll, ll> best = {0, -1};
  for (ll j = optl; j <= min(mid - 1, optr); ++j) {
    ll val = dp[j][k - 1] + profit[mid][j]; 
    if (val > best.first) {
      best = {val, j};
    }
  }
  dp[mid][k] = best.first;
  ll opt = best.second;

  dc(l, mid - 1, optl, opt, k);
  dc(mid + 1, r, opt, optr, k);
}

void calc_dp() {
  for (ll i = 1; i <= c; ++i)
    dp[i][1] = profit[i][0]; 

  for (ll k = 2; k <= c; ++k) {
    dc(1, c, 0, c - 1, k); 
  }
}
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);
    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;
      |                ~~~~~^~~

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