Submission #1263836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263836		LIA	Nafta (COI15_nafta)	C++17	34 / 100	1079 ms	97440 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 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;
      |                ~~~~~^~~

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