Submission #137358

#	Time	Username	Problem	Language	Result	Execution time	Memory
137358		Milki	Nafta (COI15_nafta)	C++14	11 / 100	16 ms	4728 KiB

nafta

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 2e3 + 5;

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

int n, m, pref[MAXN], dp[MAXN][MAXN], cost[MAXN], subtract[MAXN][MAXN];
char c[MAXN][MAXN];
bool bio[MAXN][MAXN];

int val(char t){
  return t - '0';
}

void bfs(int x, int y){
  queue <point> Q;
  Q.push(point(x, y));
  bio[x][y] = true;

  set<int> S;
  int sum = 0;
  while(!Q.empty()){
    point kord = Q.front(); Q.pop();
    x = kord.first, y = kord.second;
    S.insert(y);
    sum += val(c[x][y]);

    REP(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m || bio[nx][ny] || c[nx][ny] == '.')
        continue;

      Q.push(point(nx, ny));
      bio[nx][ny] = true;
    }
  }

  int mini = *S.begin();
  for(auto it : S){
    cost[it] += sum;

    subtract[it][mini] += sum;
    subtract[it][it] -= sum;
  }

}

int real_cost(int x, int y){
  return cost[x] - subtract[x][y];
}

const int inf = 1e9;

void solve(int lo, int hi, int plo, int phi, int pos){
  if(lo > hi) return;

  int mid = (lo + hi) >> 1;
  int ret = -inf, piv = -1;

  FOR(i, plo, min(phi, mid - 1) + 1){
    if(ret < dp[pos - 1][i] + real_cost(mid, i)){
      ret = dp[pos - 1][i] + real_cost(mid, i);
      piv = i;
    }
  }

  dp[pos][mid] = ret;
  solve(lo, mid - 1, plo, piv, pos); solve(mid + 1, hi, piv, phi, pos);
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> m;
  REP(i, n) REP(j, m) cin >> c[i][j];

  REP(i, n) REP(j, m){
    if(c[i][j] != '.' && !bio[i][j])
      bfs(i, j);
  }
  REP(i, m) FOR(j, 1, m)
    subtract[i][j] += subtract[i][j - 1];

  int sol = 0;
  dp[1][0] = cost[0];
  FOR(i, 1, m){
    dp[1][i] = cost[i];
    sol = max(sol, cost[i]);
  }
  cout << sol << "\n";

  FOR(i, 2, m + 1){
    solve(0, m - 1, 0, m - 1, i);

    sol = 0;
    REP(j, m)
      sol = max(sol, dp[i][j]);
    cout << sol << "\n";
  }
}

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