oj.uz

Submission #1052205

# Submission time Handle Problem Language Result Execution time Memory
1052205 2024-08-10T12:29:40 Z rxlfd314 Nafta (COI15_nafta) C++17
11 / 100
 1000 ms 7452 KB 
#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);
      dif[i] += dif[j];
      uf[j] = i;
      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)]};
}

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';
    }
  
  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});
    }
  
  #ifdef DEBUG
  cout << "ranges:\n";
  for (auto [a, b, c] : ranges)
    cout << a << ' ' << b << ' ' << c << '\n';
  #endif
  
  sort(all(ranges), [&](const ari3 &a, const ari3 &b) {
    return a[1] < b[1];    
  });
  
  FOR(i, 1, M) {
    long double lo = 0, hi = 1e9;
    FOR(_, 1, 40) {
      long double mid = (lo + hi) / 2.0;
      if (calc(mid).second <= i)
        hi = mid;
      else
        lo = mid;
    }
    auto [v, c] = calc(lo);
    #ifdef DEBUG
    cout << i << ": " << c << ' ' << lo << ' ' << v << ' ';
    #endif
    cout << (ll)round(v + 1ll * lo * i) << '\n';
  }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4696 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 9 ms 4444 KB Output is correct
5 Correct 4 ms 4684 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Execution timed out 1069 ms 7452 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4696 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 9 ms 4444 KB Output is correct
5 Correct 4 ms 4684 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Execution timed out 1069 ms 7452 KB Time limit exceeded
8 Halted 0 ms 0 KB -