Submission #1263824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263824		LIA	Nafta (COI15_nafta)	C++17	34 / 100	1094 ms	339008 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>> Ls(c + 2), PS(c + 2);
  for (ll i = 1; i <= c; ++i) {
    vector<pair<ll, ll>> tmp;
    tmp.reserve(ranges.size());
    for (auto [L, R, W] : ranges) {
      if (R >= i)
        tmp.push_back({L, W});
    }
    sort(tmp.begin(), tmp.end(),
         [](const pair<ll, ll> &a, const pair<ll, ll> &b) {
           return a.first < b.first;
         });
    Ls[i].resize(tmp.size());
    PS[i].resize(tmp.size());
    ll s = 0;
    for (size_t t = 0; t < tmp.size(); ++t) {
      Ls[i][t] = tmp[t].first;
      s += tmp[t].second;
      PS[i][t] = s;
    }
  }

  auto sum_leq = [&](const vector<ll> &Lvec, const vector<ll> &pref,
                     ll x) -> ll {
    if (Lvec.empty())
      return 0;
    auto it = upper_bound(Lvec.begin(), Lvec.end(), x); 
    if (it == Lvec.begin())
      return 0;
    size_t idx = size_t(it - Lvec.begin() - 1);
    return pref[idx];
  };

  vector<vector<ll>> dp(c + 1, vector<ll>(c + 1, 0));
  for (ll t = 1; t <= c; ++t) {
    for (ll i = 1; i <= c; ++i) {
      ll best = 0;
      ll total_to_i = sum_leq(Ls[i], PS[i], i); 
      for (ll k = 0; k < i; ++k) {
        ll total_to_k = sum_leq(Ls[i], PS[i], k); 
        ll gain = total_to_i - total_to_k;       
        best = max(best, dp[t - 1][k] + gain);
      }
      dp[t][i] = best;
    }
  }

  ll pref_ans = 0;
  for (ll t = 1; t <= c; ++t) {
    ll best = 0;
    for (ll i = 1; i <= c; ++i)
      best = max(best, dp[t][i]);
    pref_ans = max(pref_ans, best);
    cout << pref_ans << "\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();
}

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