Submission #1286603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286603		julia_08	Nafta (COI15_nafta)	C++20	100 / 100	257 ms	122168 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e3 + 10;

int marc[MAXN][MAXN], cnt[MAXN][MAXN], sum[MAXN][MAXN];

int dp[MAXN][MAXN];

char a[MAXN][MAXN];

int n, m;

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

bool check(int x, int y){
  return 0 < x && x <= n && 0 < y && y <= m && a[x][y] != '.';
}

void dfs(int x, int y, int &l, int &r, int &cur){

  marc[x][y] = 1;

  l = min(l, y); r = max(r, y);
  cur += a[x][y] - '0';

  for(int k=0; k<4; k++){

    int nx = x + dx[k], ny = y + dy[k];

    if(!check(nx, ny) || marc[nx][ny]) continue;

    dfs(nx, ny, l, r, cur);

  }

}

void compute(int k, int l, int r, int opt_l, int opt_r){

  if(l > r) return;

  int m = (l + r) / 2;

  pair<int, int> best = {0, 0};

  for(int i=opt_l; i<=min(m - 1, opt_r); i++) best = max(best, {dp[k - 1][i] + sum[i][m], i});

  dp[k][m] = best.first;

  compute(k, l, m - 1, opt_l, best.second);
  compute(k, m + 1, r, best.second, opt_r);

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  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(marc[i][j] || a[i][j] == '.') continue;

      int l = j, r = j, cur = 0;

      dfs(i, j, l, r, cur);
      
      cnt[l][l] += cur;
      cnt[l][r + 1] -= cur;

    }
  }

  for(int i=1; i<=m; i++){
    for(int j=1; j<=m; j++){
      cnt[i][j] += cnt[i][j - 1];
    }
  }

  for(int i=m; i>=0; i--){
    for(int j=i; j<=m; j++){
      sum[i][j] = sum[i + 1][j] + cnt[i + 1][j];
    }
  }

  for(int k=1; k<=m; k++){

    compute(k, 1, m, 0, m);

    int ans = 0;

    for(int i=1; i<=m; i++) ans = max(ans, dp[k][i]);

    cout << ans << "\n";

  }

  return 0;
}

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