oj.uz

Submission #333955

# Submission time Handle Problem Language Result Execution time Memory
333955 2020-12-08T03:58:25 Z VROOM_VARUN Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 105672 KB 
/*
ID: varunra2
LANG: C++
TASK: nafta
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, m;

int hsh(int u, int v) { return u * m + v; }

int hsh(PII u) { return u.x * m + u.y; }

PII unhsh(int u) { return MP(u / m, u % m); }

int xunhsh(int u) { return u % m; }

struct dsu {
  int n;
  VI par;
  VI siz;
  VI cost;

  void init(int _n) {
    n = _n;
    siz.assign(n, 1);
    par.resize(n);
    cost.resize(n, 0);
    iota(all(par), 0);
  }

  void set(int ind, int val) { cost[ind] = val; }

  int find(int x) {
    while (par[x] != par[par[x]]) par[x] = par[par[x]];
    return par[x];
  }

  bool same(int x, int y) { return find(x) == find(y); }

  void merge(int x, int y) {
    if (same(x, y)) return;
    x = find(x);
    y = find(y);
    if (siz[x] < siz[y]) swap(x, y);
    par[y] = x;
    siz[x] += siz[y];
    cost[x] += cost[y];
  }

  int gcost(int x) { return cost[find(x)]; }
} dsu1;

VVI grid;
VVI cost;
VI sum;
vector<vector<bool>> vis;
int gp = 0;
VVI group;
VI sums;
VII start;

VI dx = {0, -1, 0, 1};
VI dy = {1, 0, -1, 0};

bool inbnds(int i, int j) { return i >= 0 and i < n and j >= 0 and j < m; }

void dfs(int nx, int ny) {
  if (!inbnds(nx, ny)) return;
  if (grid[nx][ny] == -1) return;
  if (vis[nx][ny]) return;
  vis[nx][ny] = true;
  group[nx][ny] = gp;
  sums.back() += grid[nx][ny];
  for (int dir = 0; dir < 4; dir++) {
    dfs(nx + dx[dir], ny + dy[dir]);
  }
}

void calc(int ind) {
  SETI use;
  for (int i = 0; i < n; i++) {
    if (vis[i][ind]) use.insert(group[i][ind]);
  }
  int sum = 0;
  trav(x, use) sum += sums[x];
  VVI events;
  for (int i = 0; i < ind; i++) {
    events.PB({i, 1});
  }
  trav(x, use) { events.PB({start[x].y, 0, -sums[x]}); }
  cost[ind + 1][0] = sum;
  sort(all(events));

  trav(x, events) {
    if (x[1] == 0) {
      sum += x[2];
    } else
      cost[ind + 1][x[0] + 1] = sum;
  }
}
vector<long long> dp_before, dp_cur;

void init() {
  grid.resize(n);
  trav(x, grid) x.resize(m);
  cost.resize(m + 1);
  trav(x, cost) x.assign(m + 1, 0);
  dp_before.assign(m + 1, 0);
  dp_cur.assign(m + 1, 0);
  group.resize(n);
  trav(x, group) x.resize(m);
  vis.resize(n);
  trav(x, vis) x.assign(m, false);
}

long long C(int i, int j) { return cost[j][i]; }

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  pair<int, int> best = {-1, -1};

  for (int k = optl; k <= min(mid, optr); k++) {
    best = max(best, {dp_before[k] + C(k, mid), k});
  }

  dp_cur[mid] = best.first;
  int opt = best.second;

  compute(l, mid - 1, optl, opt);
  compute(mid + 1, r, opt, optr);
}

void compute1() {
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= i; j++) {
      dp_cur[i] = max(dp_cur[i], dp_before[j] + C(j, i));
    }
  }
}

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

  cin >> n >> m;
  init();
  dsu1.init(n * m);

  rep(i, 0, n) rep(j, 0, m) {
    char c;
    cin >> c;
    if (c == '.')
      grid[i][j] = -1;
    else
      grid[i][j] = c - '0';
    // dsu1.set(hsh(i, j), grid[i][j]);
  }

  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      if (vis[i][j]) continue;
      if (grid[i][j] == -1) continue;
      sums.PB(0);
      start.PB(MP(i, j));
      dfs(i, j);
      gp++;
    }
  }

  for (int i = 0; i < m; i++) {
    calc(i);
  }

  for (int i = 0; i < m; i++) {
    compute(0, m, 0, m);
    cout << *max_element(all(dp_cur)) << '\n';
    swap(dp_cur, dp_before);
  }

  return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 18 ms 2924 KB Output is correct
8 Correct 22 ms 2796 KB Output is correct
9 Correct 17 ms 3948 KB Output is correct
10 Correct 19 ms 2796 KB Output is correct
11 Correct 18 ms 2668 KB Output is correct
12 Correct 18 ms 2668 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 18 ms 2924 KB Output is correct
8 Correct 22 ms 2796 KB Output is correct
9 Correct 17 ms 3948 KB Output is correct
10 Correct 19 ms 2796 KB Output is correct
11 Correct 18 ms 2668 KB Output is correct
12 Correct 18 ms 2668 KB Output is correct
13 Correct 958 ms 105672 KB Output is correct
14 Execution timed out 1043 ms 104672 KB Time limit exceeded
15 Halted 0 ms 0 KB -