이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
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});
}
sort(all(ranges), [&](const ari3 &a, const ari3 &b) {
return a[1] < b[1];
});
FOR(i, 1, M) {
long double lo = 0, hi = 2e6;
FOR(_, 1, 28) {
long double mid = (lo + hi) / 2.0;
if (calc(mid).second <= i)
hi = mid;
else
lo = mid;
}
auto [v, c] = calc(lo);
cout << (ll)round(v + 1ll * lo * i) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |