Submission #1081423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081423		juicy	Nafta (COI15_nafta)	C++17	100 / 100	193 ms	134148 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2005;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int n, m, mi, ma, tot;
int c[N][N], dp[N][N], opt[N][N], res[N];
char a[N][N];
bool vis[N][N];

bool inside(int i, int j) {
  return 0 < i && i <= n && 0 < j && j <= m && a[i][j] != '.';
}

void dfs(int i, int j) {
  ma = max(ma, j); mi = min(mi, j);
  tot += a[i][j] - '0';
  vis[i][j] = 1;
  for (int dr = 0; dr < 4; ++dr) {
    int u = i + dx[dr], v = j + dy[dr];
    if (inside(u, v) && !vis[u][v]) {
      dfs(u, v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (inside(i, j) && !vis[i][j]) {
        mi = ma = j;
        tot = 0;
        dfs(i, j);
        for (int k = mi; k <= ma; ++k) {
          c[k][mi - 1] += tot;
        }
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = i - 1; j >= 0; --j) {
      c[i][j] += c[i][j + 1];
    }
  }
  for (int i = 1; i <= m; ++i) {
    dp[i][i] = dp[i - 1][i - 1] + c[i][i - 1];
    opt[i][i] = i - 1;
    res[i] = max(res[i], dp[i][i]);
    for (int j = i - 1; j > 0; --j) {
      for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; ++k) {
        if (dp[i][j] <= dp[k][j - 1] + c[i][k]) {
          dp[i][j] = dp[k][j - 1] + c[i][k];
          opt[i][j] = k;
        }
      }
      res[j] = max(res[j], dp[i][j]);
    }
  }
  for (int i = 1; i <= m; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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