oj.uz

Submission #1052247

# Submission time Handle Problem Language Result Execution time Memory
1052247 2024-08-10T12:43:16 Z rxlfd314 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 26180 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);
      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';
    }
  
  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];    
  });
  
  bool flag = false;
  FOR(i, 1, M) {
    if (flag) {
      cout << tot << '\n';
      continue;
    }
    long double lo = 0, hi = 1.5e6;
    FOR(_, 1, 26) {
      long double mid = (lo + hi) / 2.0;
      if (calc(mid).second <= i)
        hi = mid;
      else
        lo = mid;
    }
    auto [v, c] = calc(lo);
    ll ans = round(v + lo * i);
    cout << ans << '\n';
    if (ans == tot)
      flag = true;
  }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4696 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 5 ms 4692 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 854 ms 7452 KB Output is correct
8 Correct 472 ms 7384 KB Output is correct
9 Correct 65 ms 8028 KB Output is correct
10 Correct 529 ms 7400 KB Output is correct
11 Correct 30 ms 7260 KB Output is correct
12 Correct 4 ms 7260 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4696 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 5 ms 4692 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 854 ms 7452 KB Output is correct
8 Correct 472 ms 7384 KB Output is correct
9 Correct 65 ms 8028 KB Output is correct
10 Correct 529 ms 7400 KB Output is correct
11 Correct 30 ms 7260 KB Output is correct
12 Correct 4 ms 7260 KB Output is correct
13 Execution timed out 1090 ms 26180 KB Time limit exceeded
14 Halted 0 ms 0 KB -