oj.uz

Submission #1052309

# Submission time Handle Problem Language Result Execution time Memory
1052309 2024-08-10T13:14:16 Z rxlfd314 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 26920 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
 
constexpr int mxN = 2005;
int N, M, grid[mxN][mxN];
 
bool seen[mxN][mxN];
constexpr int dir[5] = {1, 0, -1, 0, 1};
int L, R, sum;
void dfs(int i, int j) {
  if (i < 0 || i >= N || j < 1 || j > M || seen[i][j] || grid[i][j] < 0)
    return;
  L = min(L, j), R = max(R, j);
  sum += grid[i][j];
  seen[i][j] = true;
  FOR(k, 0, 3)
    dfs(i + dir[k], j + dir[k+1]);
}
 
struct DSU {
  long double dif[mxN];
  int uf[mxN], lft[mxN], cnt[mxN];
  void init() {
    memset(uf, -1, sizeof(uf));
    memset(cnt, 0, sizeof(cnt));
    fill(dif, dif+M+1, 0.0);
    iota(lft, lft+M+1, 0);
  }
  int find(int i) {
    return uf[i] < 0 ? i : uf[i] = find(uf[i]);
  }
  void compress(int i) {
    while (lft[i] > 0 && dif[i] >= 0) {
      int j = find(lft[i] - 1);
      if (uf[i] > uf[j])
        swap(i, j);
      dif[i] += dif[j];
      uf[i] += uf[j];
      uf[j] = i;
      cnt[i] = max(cnt[i], cnt[j]);
      lft[i] = min(lft[i], lft[j]);
    }
  }
} uf;
 
vt<ari3> ranges;
 
pair<long double, int> calc(long double pen) {
  uf.init();
  int j = 0;
  FOR(i, 1, M) {
    int k = uf.find(0);
    uf.dif[i] += uf.dif[k] - pen;
    uf.dif[i+1] -= uf.dif[k] - pen;
    uf.cnt[i] = uf.cnt[k] + 1;
    uf.compress(i);
    for (; j < size(ranges) && ranges[j][1] == i; j++) {
      k = uf.find(ranges[j][0]);
      uf.dif[k] += ranges[j][2];
      uf.dif[i+1] -= ranges[j][2];
      uf.compress(k);
    }
  }
  return {uf.dif[uf.find(0)], uf.cnt[uf.find(0)]};
}
 
void solve(int l, int r, long double vl, long double vr) {
  if (l > r)
    return;
  long double lo = vl, hi = vr;
  int m = l + r >> 1;
  FOR(_, 1, 23) {
    long double mid = (lo + hi) / 2.0;
    int v = calc(mid).second;
    if (v < m)
      hi = mid;
    else if (v > m)
      lo = mid;
    else {
      lo = mid;
      break;
    }
  }
  solve(l, m-1, lo, vr);
  
  cout << (ll)round(calc(lo).first + lo * m) << '\n';
  
  solve(m+1, r, vl, lo);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> M;
  FOR(i, 0, N-1)
    FOR(j, 1, M) {
      char c; cin >> c;
      grid[i][j] = (c == '.') ? -1 : c - '0';
    }
  
  ll tot = 0;
  FOR(i, 0, N-1)
    FOR(j, 1, M) {
      if (seen[i][j] || grid[i][j] < 0)
        continue;
      L = M, R = sum = 0;
      dfs(i, j);
      ranges.push_back({L, R, sum});
      tot += sum;
    }
  
  sort(all(ranges), [&](const ari3 &a, const ari3 &b) {
    return a[1] < b[1];    
  });
  
  solve(1, M, 0, 1.5e6);
}

Compilation message

nafta.cpp: In function 'void solve(int, int, long double, long double)':
nafta.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 311 ms 7452 KB Output is correct
8 Correct 174 ms 7260 KB Output is correct
9 Correct 70 ms 8152 KB Output is correct
10 Correct 214 ms 7396 KB Output is correct
11 Correct 128 ms 7288 KB Output is correct
12 Correct 75 ms 7252 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 311 ms 7452 KB Output is correct
8 Correct 174 ms 7260 KB Output is correct
9 Correct 70 ms 8152 KB Output is correct
10 Correct 214 ms 7396 KB Output is correct
11 Correct 128 ms 7288 KB Output is correct
12 Correct 75 ms 7252 KB Output is correct
13 Execution timed out 1041 ms 26920 KB Time limit exceeded
14 Halted 0 ms 0 KB -