oj.uz

Submission #1081423

# Submission time Handle Problem Language Result Execution time Memory
1081423 2024-08-30T04:39:25 Z juicy Nafta (COI15_nafta) C++17
100 / 100
 193 ms 134148 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 6 ms 12124 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 6 ms 13916 KB Output is correct
10 Correct 4 ms 12080 KB Output is correct
11 Correct 5 ms 13660 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 6 ms 12124 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 6 ms 13916 KB Output is correct
10 Correct 4 ms 12080 KB Output is correct
11 Correct 5 ms 13660 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 95 ms 54592 KB Output is correct
14 Correct 125 ms 54544 KB Output is correct
15 Correct 193 ms 134148 KB Output is correct
16 Correct 81 ms 54608 KB Output is correct
17 Correct 71 ms 54612 KB Output is correct
18 Correct 72 ms 54724 KB Output is correct