oj.uz

Submission #137360

# Submission time Handle Problem Language Result Execution time Memory
137360 2019-07-27T13:51:39 Z Milki Nafta (COI15_nafta) C++14
100 / 100
 622 ms 43816 KB 
#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];
}

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

  int mid = (lo + hi) >> 1;
  int ret = 0, 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;

  REP(i, 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.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 12 ms 4600 KB Output is correct
8 Correct 14 ms 4600 KB Output is correct
9 Correct 16 ms 4600 KB Output is correct
10 Correct 11 ms 4732 KB Output is correct
11 Correct 11 ms 4828 KB Output is correct
12 Correct 11 ms 4728 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 12 ms 4600 KB Output is correct
8 Correct 14 ms 4600 KB Output is correct
9 Correct 16 ms 4600 KB Output is correct
10 Correct 11 ms 4732 KB Output is correct
11 Correct 11 ms 4828 KB Output is correct
12 Correct 11 ms 4728 KB Output is correct
13 Correct 406 ms 43480 KB Output is correct
14 Correct 467 ms 43512 KB Output is correct
15 Correct 622 ms 43816 KB Output is correct
16 Correct 341 ms 43612 KB Output is correct
17 Correct 401 ms 43512 KB Output is correct
18 Correct 377 ms 43564 KB Output is correct